203.?移除鏈表元素

• 方法：添加一個虛擬節點，這不用考慮頭節點刪除情況

public ListNode removeElements(ListNode head, int val) {// 虛擬節點，指向頭節點ListNode dummy = new ListNode(0);dummy.next = head;ListNode p = dummy;// 找到被刪除節點的前一個節點，進行刪除while (p.next != null) {// 若相等，則移除元素if (p.next.val == val) {p.next = p.next.next;}else {p = p.next;}}return dummy.next;
}

707.?設計鏈表

• 帶有

class ListNode{int val;ListNode next;ListNode(){};ListNode(int val) {this.val = val;}
}class MyLinkedList {int size;ListNode dummy;// 初始化鏈表public MyLinkedList() {size = 0;dummy = new ListNode(0);}public int get(int index) {if (index < 0 || index >= size) {return -1;}ListNode cur = dummy;for (int i = index; i > 0; --i){cur = cur.next;}return cur.next.val;}public void addAtHead(int val) {ListNode node = new ListNode(val);node.next = dummy.next;dummy.next = node;size++;}public void addAtTail(int val) {// 找到最后一個元素ListNode cur = dummy;ListNode node = new ListNode(val);while (cur.next != null) {cur = cur.next;}cur.next = node;size++;}public void addAtIndex(int index, int val) {if (index > size) return;// 找到第index個節點之前ListNode cur = dummy;ListNode node = new ListNode(val);for (int i = index; i > 0; --i){cur = cur.next;}node.next = cur.next;cur.next = node;size++;}public void deleteAtIndex(int index) {if (index < 0 || index >= size) return;ListNode cur = dummy;if (index == 0) {dummy = dummy.next;}for (int i = index; i > 0; --i){cur = cur.next;}cur.next = cur.next.next;size--;}
}

反轉鏈表

1. 雙指針法

public static ListNode reverseList(ListNode head) {// 輸入：head = [1,2,3,4,5]//輸出：[5,4,3,2,1]ListNode pre = null;ListNode cur = head;while (cur != null) {ListNode tmp = cur.next;// 反轉cur.next = pre;// 迭代當前指向pre = cur;cur = tmp;}return pre;
}

2. 迭代法

public static ListNode reverseList(ListNode head) {// 輸入：head = [1,2,3,4,5]//輸出：[5,4,3,2,1]return reverse(null,head);
}public static ListNode reverse(ListNode pre,ListNode cur){if (cur == null) {return pre;}ListNode tmp = cur.next;cur.next = pre;return reverse(cur,tmp);
}