鏈表專題

/*** 鏈表的節點* @param <E>*/
public class ListNode<E> {public E element;public ListNode<E> next;public ListNode() {}public ListNode(E element) {this.element = element;}public ListNode(E element, ListNode<E> next) {this.element = element;this.next = next;}@Overridepublic String toString() {return "ListNode{" +"element=" + element +", next=" + next +'}';}
}

鏈表結構

public class MyLinkedList<E> {private ListNode<E> head;public ListNode<E> getHead() {return head;}public void setHead(ListNode<E> head){this.head = head;}public void add(E data) {ListNode<E> newNode = new ListNode<>(data);if (head == null) {head = newNode;return;}ListNode<E> curr = head;while (curr.next != null) curr = curr.next;curr.next = newNode;}@Overridepublic String toString() {StringBuilder sb = new StringBuilder();ListNode<E> curr = this.head;while (curr != null) {sb.append(curr.element).append("-->");curr = curr.next;}sb.delete(sb.length() - 3, sb.length());return sb.toString();}
}

經典問題

反轉鏈表II

問題

[力扣92] 92. 反轉鏈表 II - 力扣（LeetCode）

問題描述

給你單鏈表的頭指針 head 和兩個整數 left 和 right ，其中 left <= right 。請你反轉從位置 left 到位置 right 的鏈表節點，返回 反轉后的鏈表 。

示例 1：

輸入：head = [1,2,3,4,5], left = 2, right = 4
輸出：[1,4,3,2,5]

示例 2：

輸入：head = [5], left = 1, right = 1
輸出：[5]

解決方案

定義虛擬頭節點dummy, 要操作節點的前一個節點pre（默認為null）, 尋找的反轉節點的前一個節點first（默認指向dummy節點）

index記錄查找到left的步數，tips：left位置從1開始計算，所以我們要尋找的位置應該left-1;

移動first索引查找要操作的元素的前一個節點(節點1)。

記錄當前要操作的節點curr，使用curr對要求的節點進行反轉操作。

1. Node next = curr.next;
2. curr.next = pre;
3. pre = curr;
4. curr = next;

重復執行操作2,3,4節點，出循環后

1. first.next.next = curr; //即節點2 連接節點5
2. first.next = pre； //即節點1連接要操作的最后一個節點

ListNode<Integer> dummy = new ListNode<>(-1, head);
ListNode<Integer> pre = null;
ListNode<Integer> first = dummy;for (int i = 0; i < left - 1; i++) {first = first.next;
}ListNode<Integer> curr = first.next;for (int i = 0; i <= (right - left); i++) {ListNode<Integer> next = curr.next;curr.next = pre;pre = curr;curr = next;
}first.next.next = curr;
first.next = pre;return dummy.next;

---

刪除鏈表中中重復元素

問題

[力扣83] 83. 刪除排序鏈表中的重復元素 - 力扣（LeetCode）

問題描述

給定一個已排序的鏈表的頭 head ， 刪除所有重復的元素，使每個元素只出現一次 。返回 已排序的鏈表 。

示例 1：

輸入：head = [1,1,2]
輸出：[1,2]

示例 2：

輸入：head = [1,1,2,3,3]
輸出：[1,2,3]

解決方案

定義要移動的節點curr: curr = head

如果當前curr的值與curr.next的值相等，則斷開此節點連接下一個節點(2),否則移動curr索引

if（curr.val == curr.next.val) curr.next = curr.next.next;
else

curr = curr.next;

 public ListNode deleteDuplicates(ListNode head) {ListNode dummy = new ListNode(-1, head);ListNode curr = dummy.next;while (curr.next != null) {if (curr.val == curr.next.val) {curr.next = curr.next.next;} else {curr = curr.next;}}return dummy.next;}

刪除鏈表中節點

問題

[力扣237] 237. 刪除鏈表中的節點 - 力扣（LeetCode）

問題描述

有一個單鏈表的 head，我們想刪除它其中的一個節點 node。給你一個需要刪除的節點 node 。你將 無法訪問 第一個節點 head。

鏈表的所有值都是 唯一的，并且保證給定的節點 node 不是鏈表中的最后一個節點。刪除給定的節點。注意，刪除節點并不是指從內存中刪除它。這里的意思是：

• 給定節點的值不應該存在于鏈表中。
• 鏈表中的節點數應該減少 1。
• node 前面的所有值順序相同。
• node 后面的所有值順序相同。

自定義測試：

• 對于輸入，你應該提供整個鏈表 head 和要給出的節點 node。node 不應該是鏈表的最后一個節點，而應該是鏈表中的一個實際節點。
• 我們將構建鏈表，并將節點傳遞給你的函數。
• 輸出將是調用你函數后的整個鏈表。

示例 1：

輸入：head = [4,5,1,9], node = 5
輸出：[4,1,9]
解釋：指定鏈表中值為 5 的第二個節點，那么在調用了你的函數之后，該鏈表應變為 4 -> 1 -> 9

示例 2：

輸入：head = [4,5,1,9], node = 1
輸出：[4,5,9]
解釋：指定鏈表中值為 1 的第三個節點，那么在調用了你的函數之后，該鏈表應變為 4 -> 5 -> 9

提示：

• 鏈表中節點的數目范圍是 [2, 1000]
• -1000 <= Node.val <= 1000
• 鏈表中每個節點的值都是 唯一 的
• 需要刪除的節點 node 是 鏈表中的節點 ，且 不是末尾節點

解決方案

---

 public void deleteNode(ListNode node) {node.val=node.next.val;node.next=node.next.next;}

移除鏈表元素

問題

[力扣203] 203. 移除鏈表元素 - 力扣（LeetCode）

問題描述

給你一個鏈表的頭節點 head 和一個整數 val ，請你刪除鏈表中所有滿足 Node.val == val 的節點，并返回 新的頭節點 。

示例 1：

輸入：head = [1,2,6,3,4,5,6], val = 6
輸出：[1,2,3,4,5]

示例 2：

輸入：head = [], val = 1
輸出：[]

示例 3：

輸入：head = [7,7,7,7], val = 7
輸出：[]

解決方案

遞歸退出條件 :if(curr.next ==null) return null;

curr.next = null;

判斷當前節點是否是要刪除的節點,如果是則刪除(即斷開下一個節點的連接)

if(curr.val == val){

return curr.next;

}else{

return curr;

}

遞歸操作

public ListNode<Integer> removeElementsx(ListNode<Integer> curr, int val) {if (curr == null) return null;curr.next = removeElementsx(curr.next,val);if(curr.val == val ){return curr.next;}else{return curr;}
}

---

移除鏈表元素II

問題

[力扣82] 82. 刪除排序鏈表中的重復元素 II - 力扣（LeetCode）

問題描述

給定一個已排序的鏈表的頭 head ， 刪除原始鏈表中所有重復數字的節點，只留下不同的數字 。返回 已排序的鏈表 。

示例 1：

輸入：head = [1,2,3,3,4,4,5]
輸出：[1,2,5]

示例 2：

輸入：head = [1,1,1,2,3]
輸出：[2,3]

解決方案

定義虛擬頭結點dummy，操作節點curr指向dummy

移動curr，防止越界 curr.next !=null && curr.next.next!=null,

獲取當前節點，使用中間節點tmp記錄 ListNode tmp = curr.next;

判斷是和相鄰的節點是否相等（curr.next.next: 節點2）

if(curr.next.next.val ==val){

//循環刪除節點

while(curr.next !=null && curr.next.val == val){

? curr.next = curr.next.next;

? }

}

---

從鏈表中移除節點

問題

[力扣2487] 2487. 從鏈表中移除節點 - 力扣（LeetCode）

題目描述

給你一個鏈表的頭節點 head 。移除每個右側有一個更大數值的節點。返回修改后鏈表的頭節點 head 。

示例 1：

輸入：head = [5,2,13,3,8]
輸出：[13,8]
解釋：需要移除的節點是 5 ，2 和 3 。
- 節點 13 在節點 5 右側。
- 節點 13 在節點 2 右側。
- 節點 8 在節點 3 右側。

示例 2：

輸入：head = [1,1,1,1]
輸出：[1,1,1,1]
解釋：每個節點的值都是 1 ，所以沒有需要移除的節點。

解決方案

---

給你一個鏈表的頭節點 head 。移除每個右側有一個更大數值的節點。返回修改后鏈表的頭節點 head 。

示例 1：

[外鏈圖片轉存中…(img-1wS0djH7-1739015221466)]

輸入：head = [5,2,13,3,8]
輸出：[13,8]
解釋：需要移除的節點是 5 ，2 和 3 。
- 節點 13 在節點 5 右側。
- 節點 13 在節點 2 右側。
- 節點 8 在節點 3 右側。

示例 2：

輸入：head = [1,1,1,1]
輸出：[1,1,1,1]
解釋：每個節點的值都是 1 ，所以沒有需要移除的節點。

解決方案