代码随想录二刷day03

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

一、力扣203. 移除链表元素

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode removeElements(ListNode head, int val) {ListNode list = new ListNode();list.next = head;ListNode p = head, pre = list;while(p != null){if(p.val == val){pre.next = p.next;p = p.next;}else{pre = p;p = p.next;}}return list.next;}
}

二、力扣707. 设计链表

class MyLinkedList {int size;DLinkList head, tail;public MyLinkedList() {this.size = 0;this.head = new DLinkList(0);this.tail = new DLinkList(0);this.head.next = this.tail;this.tail.prev = this.head;}public int get(int index) {if(index < 0 || index >= this.size){return -1;}DLinkList p = head;int i = 0;while(i <= index){i ++;p = p.next;}return p.val;}public void addAtHead(int val) {addAtIndex(0, val);}public void addAtTail(int val) {addAtIndex(this.size, val);}public void addAtIndex(int index, int val) {if(index < 0 || index > this.size){return ;}DLinkList node = new DLinkList(val);int i = 0;DLinkList p = head;while(i < index){i ++;p = p.next;}node.next = p.next;p.next.prev = node;node.prev = p;p.next = node;this.size ++;}public void deleteAtIndex(int index) {if(index < 0 || index > this.size-1){return;}DLinkList p = head;int i = 0;while(i < index){i ++;p = p.next;}p.next.next.prev = p;p.next = p.next.next;this.size --;}
}
class DLinkList{int val;DLinkList prev;DLinkList next;DLinkList(int val){this.val = val;this.prev = null;this.next = null;}
}/*** Your MyLinkedList object will be instantiated and called as such:* MyLinkedList obj = new MyLinkedList();* int param_1 = obj.get(index);* obj.addAtHead(val);* obj.addAtTail(val);* obj.addAtIndex(index,val);* obj.deleteAtIndex(index);*/

三、力扣206. 反转链表

头插法

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseList(ListNode head) {ListNode node = new ListNode(-1, null);ListNode p = head, s;while(p != null){s = p; p = p.next;s.next = node.next;node.next = s;}return node.next;}
}

递归

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseList(ListNode head) {return reverse(null, head);}public ListNode reverse(ListNode prev, ListNode cur){if(cur == null){return prev;}ListNode p = cur.next;cur.next = prev;return reverse(cur, p);}
}

双指针法

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseList(ListNode head) {if(head == null){return head;}ListNode prev = null;ListNode cur = head;ListNode temp ;while(cur != null){temp = cur.next;cur.next = prev;prev = cur;cur = temp;}return prev;}
}