基礎數據結構之鏈表相關的一些問題
基礎數據結構之鏈表相關的一些問題
作者：Grey
原文地址：
反轉單鏈表
題目描述見：LeetCode 206. Reverse Linked List
思路如下
對於任何一個節點 cur 來說，記錄一個前驅節點 pre (第一個節點的前驅節點是 null )
先用一個臨時節點 tmp 記錄 cur 的下一個節點，然後設置
cur.next = pre;
pre = cur;
cur = tmp;
以下是示例圖
假設原始鏈表如下
第一個節點的反轉流程如下
第二個節點的反轉流程如下
最後返回 pre 節點即為反轉後的節點。
程式碼如下
class Solution {
public ListNode reverseList(ListNode cur) {
if (cur == null || cur.next == null) {
return cur;
}
ListNode pre = null;
while (cur != null) {
ListNode tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
}
時間複雜度O(N)，空間複雜度O(1)。
反轉鏈表也可以用遞歸方法來實現
定義遞歸函數 ListNode reverse(ListNode cur)，這個遞歸函數的含義是
反轉以 cur 為頭的鏈表，並把反轉後的頭節點返回。
這個遞歸函數的 base case 是，只有一個節點的時候，即
if (cur == null || cur.next == null) {
return cur;
}
這種情況下，直接返回當前節點即可。
接下來是普遍情況：
當前來到 cur 節點，c，d，e 已經完成了反轉。
此時 cur 需要做如下操作。把 c , d, e 反轉後的頭節點獲取到，假設為 pre ， 在上圖中，pre 就是 e 節點，就是反轉鏈表的頭節點。然後再做如下操作
cur.next.next = cur;
cur.next = null;
其中cur.next = null非常重要，只有這樣，才能防止出現環。完整程式碼如下
class Solution {
public ListNode reverseList(ListNode cur) {
return reverse(cur);
}
// 反轉cur為頭的鏈表，並把反轉後的頭節點返回
public ListNode reverse(ListNode cur) {
if (cur == null || cur.next == null) {
return cur;
}
ListNode pre = reverse(cur.next);
cur.next.next = cur;
cur.next = null;
return pre;
}
}
時間複雜度O(N)
空間複雜度O(N)(遞歸棧佔用的空間)
反轉雙向鏈表
雙向鏈表和單鏈表的反轉類似，每個節點要多處理一次每個節點的前驅指針，
完整程式碼如下
package snippet;
import java.util.ArrayList;
import java.util.List;
// 反轉雙向鏈表
public class Code_0008_ReverseDoubleList {
public static class DoubleNode {
public int value;
public DoubleNode last;
public DoubleNode next;
public DoubleNode(int data) {
value = data;
}
}
public static DoubleNode reverseDoubleList(DoubleNode cur) {
DoubleNode pre = null;
while (cur != null) {
DoubleNode tmp = cur.next;
cur.next = pre;
// 處理前驅指針
cur.last = tmp;
pre = cur;
cur = tmp;
}
return pre;
}
}
反轉單鏈表一部分
題目描述見：LeetCode 92. Reverse Linked List II
本題核心依然是反轉鏈表，只是增加了一些變數來記錄需要反轉鏈表的頭位置和結尾位置，不過需要注意的是，本題的鏈表開始位置是從 1 開始，所以，如果m = 1 && n != 1，說明反轉鏈表後需要返回新的頭部，只要m > 1，反轉鏈表一部分以後，返回原先的頭即可。
完整程式碼見
class Solution {
public static ListNode reverseBetween(ListNode head, int m, int n) {
if (m == n) {
// 不變
return head;
}
ListNode startPre = null;
ListNode start = null;
ListNode end;
ListNode endAfter = null;
ListNode cur = head;
int i = 1;
while (i <= n) {
if (i == m - 1) {
startPre = cur;
} else if (i == m) {
start = cur;
} else if (i == n) {
end = cur;
if (end.next != null) {
endAfter = end.next;
end.next = null;
}
}
cur = cur.next;
i++;
}
i = m;
ListNode pre = null;
// 反轉鏈表操作
while (i <= n) {
ListNode tmp = start.next;
start.next = pre;
pre = start;
start = tmp;
if (i == m) {
pre.next = endAfter;
}
i++;
}
if (m == 1 && n != 1) {
// 換頭了
return pre;
}
startPre.next = pre;
// 返回原來的頭節點即可。
return head;
}
}
在鏈表中刪除指定值的所有節點
題目鏈接：LeetCode 203. Remove Linked List Elements
主要思路就是遍歷鏈表，找到對應值的元素，就做刪除操作，對於普遍位置來說，刪除操作可以按如下方式進行
不過，需要注意一個邊界條件，就是：如果要刪除的節點就是頭節點，那麼經過刪除後，會面臨要換頭的情況。
所以在一開始的時候，需要做如下判斷
while (head != null && head.val == val) {
head = head.next;
}
即找到第一個不需要刪的節點。
完整程式碼見
class Solution {
public static ListNode removeElements(ListNode head, int val) {
if (null == head) {
return null;
}
while (head != null && head.val == val) {
head = head.next;
}
if (head == null) {
return null;
}
ListNode c = head;
ListNode n = c.next;
while (n != null) {
if (n.val == val) {
c.next = n.next;
n = n.next;
} else {
c = n;
n = c.next;
}
}
return head;
}
}
兩個鏈表相加問題
題目鏈接見：LeetCode 2. Add Two Numbers
沒有特別的演算法，就是要注意每次相加可能會有進位的問題，所以設置一個數據結構Node，用於存每一位計算的結果，包括這一位是否有進位的情況。
public static class Node {
// 當前值
public int v;
// 進位值（只能是0或者1）
public int n;
}
每次操作相加的方法封裝為如下
private static Node add(int v1, int v2) {
Node n = new Node();
// 5 + 7 = 12
// 則 當前值為：n.v = 2
// 進位值為：n.n = 1
n.v = (v1 + v2) % 10;
n.n = (v1 + v2) / 10;
return n;
}
還有一個邊界條件，由於是從左往右依次相加，所以最右側如果相加後超過了 9 ，那麼需要在最右側的右側繼續進一位。例如：
.....8
+
.....7
=
.....51 <--注意得到5以後，還要繼續向右側進1。
完整程式碼見：
class Solution {
public static class Node {
// 當前值
public int v;
// 進位值（只能是0或者1）
public int n;
}
// l1 和 l2 非空
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode result = new ListNode();
Node start = add(l1.val, l2.val);
result.val = start.v;
l1 = l1.next;
l2 = l2.next;
ListNode c = result;
while (l1 != null && l2 != null) {
start = add(l1.val + l2.val, start.n);
c.next = new ListNode(start.v);
c = c.next;
l1 = l1.next;
l2 = l2.next;
}
while (l1 != null) {
start = add(l1.val, start.n);
c.next = new ListNode(start.v);
c = c.next;
l1 = l1.next;
}
while (l2 != null) {
start = add(l2.val, start.n);
c.next = new ListNode(start.v);
c = c.next;
l2 = l2.next;
}
if (start.n != 0) {
c.next = new ListNode(1);
}
return result;
}
private static Node add(int v1, int v2) {
Node n = new Node();
n.v = (v1 + v2) % 10;
n.n = (v1 + v2) / 10;
return n;
}
}
K個節點的組內逆序調整問題
LeetCode 25. Reverse Nodes in k-Group
本題需要設計兩個方法：
第一個方法ListNode getKGroupEnd(ListNode start, int k)：從鏈表 start 位置開始，數夠 k 個位置，返回 k 個位置後的那個節點。
比如鏈表為：
...-> start -> b -> c -> d -> e
k = 3
表示從 start 開始，數夠 3 個，所以返回 c 節點
如果是下述情況
...-> start -> b -> c -> null
k = 6
由於 start 後面不夠 6 個，所以返回 null。
public static ListNode getKGroupEnd(ListNode start, int k) {
while (--k != 0 && start != null) {
start = start.next;
}
return start;
}
第二個方法void reverse(ListNode start, ListNode end)，表示反轉 start 到 end 之間的鏈表。
例如：原鏈表為：
....->a->b->c->d->e....
假設start = a, end = d
經過reverse方法，會變成
...d->c->b->a->e.....
有了上述兩個方法，我們可以比較方便實現原題要求，主流程如下
public static ListNode reverseKGroup(ListNode head, int k) {
ListNode start = head;
ListNode end = getKGroupEnd(start, k);
if (end == null) {
return head;
}
// 第一組湊齊了！
head = end;
reverse(start, end);
// 上一組的結尾節點
ListNode lastEnd = start;
while (lastEnd.next != null) {
start = lastEnd.next;
end = getKGroupEnd(start, k);
if (end == null) {
return head;
}
reverse(start, end);
lastEnd.next = end;
lastEnd = start;
}
return head;
}
快慢指針問題
題目描述見：LeetCode 876. Middle of the Linked List
本題主要解決的問題是：
如果一個鏈表中的節點個數是奇數，則返回中點；如果個數是偶數，則返回下中點。
通常這類問題都是使用快慢指針來做，思路如下
設置一個快指針 fast，一個慢指針 slow， 快指針一次走兩步，慢指針一次走一步，快指針走到結尾的時候，慢指針正好到中點位置。
完整程式碼見：
class Solution {
// [1,2,3,4,5] --> 3
// [1,2,3,4,5,6] --> 4
// 奇數返回中點，偶數返回下中點
public static ListNode middleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
快慢指針還可以解決如下類似的問題，只不過是初始化快慢指針的節點有所不同而已。
-
輸入鏈表頭節點，奇數長度返回中點，偶數長度返回上中點
-
輸入鏈表頭節點，奇數長度返回中點，偶數長度返回下中點
-
輸入鏈表頭節點，奇數長度返回中點前一個，偶數長度返回上中點前一個
-
輸入鏈表頭節點，奇數長度返回中點前一個，偶數長度返回下中點前一個
判斷鏈表是否為迴文結構
題目鏈接為：LeetCode 234. Palindrome Linked List
本題比較好理解的一種解法是使用棧的方式，先將節點全部入棧，然後依次彈出並和原鏈表一一對比。空間複雜度是O(N)。
// 利用棧O(n)
public static boolean isPalindrome(ListNode head) {
Stack<ListNode> stack = new Stack<>();
ListNode c = head;
while (c != null) {
stack.push(c);
c = c.next;
}
c = head;
while (c != null) {
if (c.val != stack.pop().val) {
return false;
}
c = c.next;
}
return true;
}
本題也可以使用鏈表操作，將空間複雜度優化為O(1)。
同時本題也需要使用快慢指針找到鏈表的中間位置，然後中間位置拆分左右兩側的鏈表來進行比較。整體流程如下圖
完整程式碼見：
class Solution {
// 修改原鏈表，空間O(1)
public static boolean isPalindrome(ListNode head) {
// 0個節點
// 1個節點 都是迴文
if (head == null || head.next == null) {
return true;
}
// 判斷兩個節點
if (head.next.next == null) {
return head.val == head.next.val;
}
// 判斷三個節點
if (head.next.next.next == null) {
return head.val == head.next.next.val;
}
//到這一步，至少有四個節點
// 使用快慢指針
// 奇數來到中點前一個位置(假設為a)和中點後一個位置(假設為b)
// 偶數來到上中點位置(假設為a)和下中點位置(假設為b)
// head ... a 這個鏈表，鏈表反轉一下 a...head
// 設置兩個指針，一個指向a，一個指向b，每個位置對比，結果記錄在result中
// 恢復整個鏈表
ListNode slow = head;
ListNode fast = head.next.next;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
ListNode a = slow;
ListNode b;
ListNode mid = null;
if (fast != null) {
// 鏈表個數為奇數
mid = a.next;
b = a.next.next;
} else {
b = a.next;
// 鏈表個數為偶數
}
// 斷開鏈表
a.next = null;
// 反轉前半部分鏈表
ListNode c = reverse(head);
boolean result = true;
ListNode leftStart = c;
ListNode rightStart = b;
while (leftStart.next != null) {
if (leftStart.val != rightStart.val) {
result = false;
}
leftStart = leftStart.next;
rightStart = rightStart.next;
}
if (leftStart.val != rightStart.val) {
result = false;
}
// leftStart來到開始節點
// rightStart來到末尾節點
ListNode cur = reverse(leftStart);
while (cur.next != null) {
cur = cur.next;
}
if (mid == null) {
cur.next = b;
} else {
cur.next = mid;
mid.next = b;
}
return result;
}
private static ListNode reverse(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
}
