一.一些經驗總結

1. 鏈表天然具有遞歸性質,單鏈表可以看做一個單叉樹,很多可以應用到二叉樹的題目也可以應用到鏈表的題目之中,下面是一個體現單鏈表遞歸性質很好的例子逆序打印鏈表的值

private void reversePrint(ListNode head) {if(head == null) return;reversePrint(head.next);System.out.println(head.val)
}

不難發現這種打印方式很像二叉樹中的后序遍歷
2. 對于鏈表的題目,思路往往很容易想到,只是過程可能有點復雜,一定要多畫圖,一定要舍得用變量

二.例題講解

01.刪除排序鏈表中重復的元素
鏈接:https://leetcode.cn/problems/remove-duplicates-from-sorted-list/description/
分析

• 這是鏈表去重的經典問題,有多種解法
• 最容易想到的解法就是使用一個去重的數據結構(Set),遍歷整個鏈表
• 最優秀的解法是一個指針,一次遍歷,注意題目條件,數組是有序的,那么重復元素一定是相鄰的,每遍歷到一個節點,就判斷cur.val == cur.next.val,如果相等,就刪除cur.next(完成一次刪除操作);如果不等,直接讓cur向后走一步即可

代碼:

/*** 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 deleteDuplicates(ListNode head) {if(head == null) return null;// 原地去重ListNode cur = head;while(cur.next != null) {if(cur.val ==cur.next.val) cur.next = cur.next.next;else cur = cur.next;// 有可能直接走到null}return head;}
}

說明:

1. 循環的條件往往是根據下面的判斷條件決定的,判斷條件是cur.val == cur.next.val,如果cur.next ==null,則會觸發空指針異常,所以循環的條件是cur.next != null,對于鏈表的最后一個元素,要么是重復元素,要么不是重復元素,如果是重復元素,則前一個節點的值和當前節點的值相等,在上一步就會執行刪除操作;如果不是重復元素,不用刪除
2. 為什么存在重復元素的情況,刪除重復元素之后不讓cur走一步?因為有可能刪除的是最后一個元素,這樣cur.next = null,如果讓cur向后走一步,在下一步的循環判斷中就會觸發空指針異常

---

刪除重復元素的進階版
鏈接:https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/description/
分析

• 本題相較于上一題,需要將所有的重復元素都刪除,而上一題是只保留重復元素的一個
• 同樣也可以采用一個指針,一次遍歷的操作,不過本題要刪除所有的重復元素,就不能讓指針走到重復元素的位置,應該走到第一個重復元素的前去節點,即判斷cur.next.val == cur.next.next.val,如果相等,則一直循環刪除所有等于cur.next.val(設為x)的所有節點,直到值不為x
• 循環條件和判斷條件的確立同上一題

代碼:

/*** 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 deleteDuplicates(ListNode head) {// 個人經驗  使用一個指針更容易理解  反而維護多個指針容易把自己繞暈if(head == null) return null;// 一次遍歷的思路ListNode phead = new ListNode(0);phead.next = head;ListNode cur = phead;while(cur.next != null && cur.next.next != null) {if(cur.next.val == cur.next.next.val) {int x = cur.next.val;while(cur.next != null && cur.next.val == x)// 一直走到值不等于x的節點cur.next = cur.next.next;}else {cur = cur.next;}}return phead.next;}
}

---

02.反轉鏈表
鏈接:https://leetcode.cn/problems/reverse-linked-list/
分析

1.方法一:使用兩個指針迭代完成局部的鏈表的反轉

/*** 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 null;ListNode pre = null, cur = head;while(cur != null) {ListNode tmp = cur.next;cur.next = pre;pre = cur;cur = tmp;}return pre;// pre此時是原鏈表的最后一個節點  反轉鏈表的頭結點}
}

2.方法2:遞歸寫法

• 你給我反轉當前節點(head)后面的所有節點,并且把反轉后的頭節點返回
• 反轉當前節點和后面的節點,將后面的節點當做一個節點即可

/*** 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 || head.next == null) return head;ListNode newHead = reverseList(head.next);// 完成一次局部的反轉head.next.next = head;head.next = null;return newHead;}
}

• 為什么返回newHead而不是head?因為newHead是完成反轉之后的新的頭結點

---

03.回文鏈表
鏈接:https://leetcode.cn/problems/palindrome-linked-list/description/
分析

方法1:棧
遇到對稱有關的問題應該先考慮能否使用stack這種數據結構解決,對稱問題最大的特點就是從前往后遍歷的結果和從后往前遍歷的結果相同,從前往后遍歷容易,關鍵在于對于某些問題從后往前遍歷很困難(比如單鏈表),這是就可以使用棧這種數據結構,充分利用棧后進先出的結構特點完成從后往前遍歷

/*** 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 boolean isPalindrome(ListNode head) {// 借助棧Stack<Integer> st = new Stack<>();ListNode i1 = head;// 1.將所有元素入棧while(i1 != null) {st.push(i1.val);i1 = i1.next;}// 2.依次出棧進行比較ListNode i2 = head;while(i2 != null) {if(st.peek() != i2.val) return false;else {i2 = i2.next;st.pop();}}return true;}
}

方法2:反轉后半部分鏈表,依次進行比較

1. 利用快慢指針找到中間節點
2. 根據fast是否為null判斷節點的個數是奇數還是偶數,如果是奇數,向前走一步:如果是偶數,無需移動
3. 反轉后面的所有節點,依次向后比較

/*** 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 boolean isPalindrome(ListNode head) {ListNode fast = head, slow = head;// 通過快慢指針找到中點while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;}// 如果fast不為空，說明鏈表的長度是奇數個if (fast != null) {slow = slow.next;}// 反轉后半部分鏈表slow = reverse(slow);fast = head;while (slow != null) {// 然后比較，判斷節點值是否相等if (fast.val != slow.val)return false;fast = fast.next;slow = slow.next;}return true;}// 反轉鏈表public ListNode reverse(ListNode head) {if(head == null || head.next == null) return head;ListNode newHead = reverse(head.next);head.next.next = head;head.next = null;return newHead;}}