LeetCode——鏈表

---

目錄

概述

找出兩個鏈表的交點

鏈表反轉

歸并兩個有序的鏈表

從有序鏈表中刪除重復節點

刪除鏈表的倒數第n個節點

交換鏈表中的相鄰節點

鏈表求和

回文鏈表

分隔鏈表

鏈表元素按奇偶聚集

---

0. 概述

鏈表是空節點，或者有一個值和一個指向下一個鏈表的指針，因此很多鏈表問題可以用遞歸來處理

---

1. 找出兩個鏈表的交點

概述

1. A和B兩個鏈表相交于c1，但不會出現相交后又分開的情況，因為每個節點只有一個next指針，也就只能有一個后繼節點

2. 思路

設A的長度為a+c，B的長度為b+c，其中c為尾部公共部分長度，可知a+c+b = b+c+a

當訪問A鏈表的指針訪問到鏈表尾部時，令它從鏈表B的頭部開始訪問鏈表B；同樣的，當訪問鏈表B的指針訪問到鏈表尾部時，令它從鏈表A的頭部開始訪問鏈表A。這樣就能控制A和B兩個鏈表的指針能同時訪問到交點

如果不存在交點那么a+b=b+a，l1和l2同時為null，從而退出循環

3. 代碼

public static ListNode getIntersectionNode(ListNode head1, ListNode head2) {ListNode l1 = head1;ListNode l2 = head2;while (l1 != l2) {l1 = l1 == null ? head2 : l1.next;l2 = l2 == null ? head1 : l2.next;}return l1;}

4. 補充

如果只是判斷是否存在交點，那么有兩種解法
1. 把第一個鏈表的結尾連接到第二鏈表的開頭，看第二鏈表是否存在環
2. 或者直接比較兩個鏈表的最后一個節點是否相同

---

2. 鏈表反轉

1. 遞歸版

思路
1. 設頭節點為head，下一個節點為next。
2. 通過遞歸reverseList(next)，所以可以到倒數第二個節點head和尾結點next。
3. 將next.next指向前一個節點head，然后再將head.next置為null。從后到前依次反轉

代碼

2. 頭插法

思路
還不太懂…

代碼

public static ListNode reverseList(ListNode head) {if (head == null || head.next == null) {return head;}ListNode next = head.next;ListNode newHead = reverseList(next);next.next = head;head.next = null;return newHead;}public static ListNode reverseList2(ListNode head) {ListNode newHead = new ListNode(-1);while (head != null) {ListNode next = head.next;head.next = newHead.next;newHead.next = head;head = next;}return newHead.next;}

---

3. 歸并兩個有序的鏈表

思路
1. 如果l1,或者l2一開始就是null，那么沒有任何操作需要合并，所以我們只需要返回非空鏈表。
2. 否則就要判斷l1和l2哪一個的頭元素更小，然后遞歸地決定下一個添加到結果里的值。
3. 如果兩個鏈表都是空的，那么過程終止，所以遞歸過程最終一定會終止

代碼

public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {if (l1 == null) {return l2;}if (l2 == null) {return l1;}if (l1.val < l2.val) {l1.next = mergeTwoLists(l1.next, l2);return l1;} else {l2.next = mergeTwoLists(l1, l2.next);return l2;}}

---

4. 從有序鏈表中刪除重復節點

1. 概述

2. 思路

直接法
1. 由于輸入的列表已排序，因此我們可以通過將結點的值與它之后的節點值進行比較來確定它是否為重復節點。如果它是重復的，則改當前節點的next指針，以便它跳到下一個節點并直接指向下一個節點之后的結點

遞歸
1. 遞歸，head.next = deleteDuplicates(head.next)，會將結點依次壓入棧中，最后取出進行比較，如果相同，則返回后一個節點，否則返回當前節點

3. 代碼

public static ListNode deleteDuplicates(ListNode head){if (head==null||head.next==null){return head;}head.next = deleteDuplicates(head.next);return head.val == head.next.val?head.next:head;}public static ListNode deleteDuplicates2(ListNode head){ListNode current = head;while (current!=null||current.next!=null){if (current.val==current.next.val){current.next = current.next.next;}else {current = current.next;}}return head;}

---

5. 刪除鏈表的倒數第n個節點

1. 概述

2. 思路

可以創建兩個指針：快指針fast和慢指針slow，快指針先走n步，然后快慢指針一起走到fast到鏈表末尾。此時慢指針slow所在位置就是需要刪除的前一個結點。

3. 代碼

public static ListNode removeNthFromEnd(ListNode head, int n) {ListNode fast = head;ListNode slow = head;while (n-- > 0) {fast = fast.next;}if (fast == null) {return head.next;}while (fast.next != null) {fast = fast.next;slow = slow.next;}slow.next = slow.next.next;return head;}

---

6. 交換鏈表中的相鄰結點

1. 概述

2. 思路

迭代
1. 創建node節點（用于記錄最后結果），next指向head，創建變量pre=node（pre用于移動鏈表下標）
2. 當pre.next!=null&&pre.next.next!=null時，創建l1為pre.next節點，l2為pre的next.next節點，記錄節點next=l2.next。然后開始交換
3. l1.next指向next，l2.next指向l1，pre.next指向l2。完成交換，移動pre位置到l1
4. 最后返回node.next

遞歸
1. 從鏈表的頭節點head開始遞歸
2. 每次遞歸都負責交換一對節點。由firstNode和secondNode表示要交換的兩個節點
3. 下一次遞歸則是傳遞下一對需要交換的節點。如鏈表還有節點，則繼續遞歸
4. 交換了兩個節點以后，返回secondNode，因為它是交換后的新頭
5. 在所有節點交換完成后，我們返回交換后的頭，實際就是原始鏈表的第二個節點

3. 代碼

public static ListNode swapPairs(ListNode head) {ListNode node = new ListNode(-1);node.next = head;ListNode pre = node;while (pre.next != null && pre.next.next != null) {ListNode l1 = pre.next;ListNode l2 = pre.next.next;ListNode next = l2.next;l1.next = next;l2.next = l1;pre.next = l2;pre = l1;}return node.next;}public static ListNode swapPairs2(ListNode head) {if (head == null || head.next == null) {return head;}ListNode first = head;ListNode second = head.next;first.next = swapPairs2(second.next);second.next = first;return second;}

---

7. 鏈表求和

1. 概述

2. 思路

創建兩個棧保存兩個鏈表的值，創建head頭節點固定待會需要創建的鏈表的頭節點，carry遍歷則記錄需要進位的數

當l1Stack或者l2Stack不為null，或者carry!=0（表示需要進位）時，進行while循環

當l1Stack不為null 則取出棧頂元素，否則為0，設為遍歷x。當l1Stack不為null 則取出棧頂元素，否則為0，設為遍歷y。sum為x+y+carry。

得出計算結果后創建新節點，節點值為sum%10，然后與頭節點相連。node.next=head.next，head.next=node

最后記錄carry需要進位值carry=sum/10

返回head.next

3. 代碼

public static ListNode addTwoNumers(ListNode l1, ListNode l2) {Stack<Integer> l1Stack = bulidStack(l1);Stack<Integer> l2Stack = bulidStack(l2);ListNode head = new ListNode(-1);int carry = 0;while (!l1Stack.isEmpty() || !l2Stack.isEmpty() || carry != 0) {int x = l1Stack.isEmpty() ? 0 : l1Stack.pop();int y = l2Stack.isEmpty() ? 0 : l2Stack.pop();int sum = x + y + carry;ListNode node = new ListNode(sum % 10);node.next = head.next;head.next = node;carry = sum / 10;}return head.next;}private static Stack<Integer> bulidStack(ListNode l) {Stack<Integer> stack = new Stack<>();while (l != null) {stack.push(l.val);l = l.next;}return stack;}

---

8. 回文鏈表

1. 概述

LeetCode234

2. 思路

方法一：將值復制到數組中后用雙指針法

復制鏈表值到數組列表中

利用雙指針法判斷是否為回文

方法二：快慢指針法（ O(n) 時間復雜度和 O(1) 空間復雜度）

創建慢指針slow=head，快指針fast=head.next，當fast不為null或者fast.next不為null時，慢指針走一步，快指針走兩步

如果fast!=null，即偶數節點，讓slow執行下一個節點

然后進行切分，當head.next=slow時，退出while循環，否則head=head.next。斷開前半部分鏈表，head.next=null

反轉后半部分鏈表，然后進行比較值

3. 代碼

public static boolean isPalindrome(ListNode head) {if (head == null || head.next == null) {return true;}ListNode slow = head, fast = head.next;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}if (fast != null) {slow = slow.next; // 偶數節點，讓slow指向下一個節點}cut(head, slow); //切成兩個鏈表return isEqual(head, reverse(slow));}private static boolean isEqual(ListNode l1, ListNode l2) {while (l1 != null && l2 != null) {if (l1.val != l2.val)return false;l1 = l1.next;l2 = l2.next;}return true;}private static ListNode reverse(ListNode head) {if (head == null || head.next == null) {return head;}ListNode next = head.next;ListNode newHead = reverse(next);next.next = head;head.next = null;return newHead;}private static void cut(ListNode head, ListNode cutNode) {while (head.next != cutNode) {head = head.next;}head.next = null;}public static boolean isPalindrome2(ListNode head) {List<Integer> list = new ArrayList<>();while (head != null) {list.add(head.val);head = head.next;}int l = 0;int r = list.size() - 1;while (l < r) {if (list.get(l) != (list.get(r))) {return false;}l++;r--;}return true;}

---

9. 分隔鏈表

1. 概述

給定一個結點為root的鏈表，編寫一個函數以將鏈表分隔為K個連續的部分。每部分的長度應該盡可能的相等：任意兩部分的長度差距不超過1，也就說可能有些部分為null，k個部分應該按照在鏈表中出現的順序進行輸出，并且排在前面的部分長度應該大于或等于后面的長度

2. 思路

創建遍歷N記錄原始鏈表長度，用于計算每個分區的鏈表長度，size=N/k（每個分區的最少長度），mod=N%k（開始的分區還需要多的個數），如長度為10的鏈表分成三個分區，第一個分區多一個元素

創建鏈表數組，容量為k，當cur結點不為null，for循環對分區進行遍歷
1. 計算每個分區的鏈表長度curSize=size+(mod-- > 0?1:0)
2. 計算出分區長度后，對cur結點進行后移

進行切分鏈表
1. 記錄cur的下一個節點為next
2. 將cur.next = null
3. cur = next

3. 代碼

public static ListNode[] splitListToParts(ListNode root, int k) {int N = 0;ListNode cur = root;while (cur!=null){N++;cur = cur.next;}int mod = N%k;int n = N/k;ListNode[] ret = new ListNode[k];cur = root;for (int i = 0;cur!=null&& i < k; i++) {ret[i] = cur;int curSize = n+(mod-->0?1:0);for (int j = 0; j < curSize - 1; j++) {cur = cur.next;}ListNode next = cur.next;cur.next = null;cur = next;}return ret;}

---

10. 鏈表元素按奇偶聚集

1. 概述

給定一個鏈表，把所有的奇數節點和偶數節點分別排在一起。這里的奇數節點和偶數節點指的是節點編號的奇偶性，而不是節點的值的奇偶性（LeetCode328）

2. 思路

一個LinkedList需要一個頭指針和一個尾指針來支持雙端操作

用變量head和odd保存奇鏈表的頭和尾指針。evenHead和even保存偶鏈表的頭和尾指針。算法會遍歷原鏈表一次并把奇節點放到奇鏈表里去、偶節點放到偶鏈表里去。

遍歷整個鏈表還需要一個指針作為迭代器。這里odd和even指針不僅僅是尾指針，也可以扮演原鏈表的迭代器角色

3. 代碼

public static ListNode oddEvenList(ListNode head) {if (head == null) {return head;}ListNode odd = head, even = head.next, evenHead = even;while (even != null && even.next != null) {odd.next = odd.next.next;odd = odd.next;even.next = even.next.next;even = even.next;}odd.next = evenHead;return head;}

總結

以上是生活随笔為你收集整理的LeetCode——链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。