面試精選之鏈表問題集錦
鏈表問題是面試過程中經常被問到的一部分，很考查編程功底。最近刷了 LeetCode 上鏈表部分的面試題，我總結了一些有代表性的鏈表問題。
本文使用的是 Java 語言，下面是所用到的鏈表節點的定義：
public class ListNode{
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
1. 在 O(1) 時間刪除鏈表節點
Leetcode 237. Delete Node in a Linked List
題目描述：給定單鏈表中需要刪除的節點（不是尾節點），在 O(1) 時間刪除該節點。
分析：本題與《編程之美》上的「從無頭單鏈表中刪除節點」類似。主要思想都是「貍貓換太子」，即用下一個節點數據覆蓋要刪除的節點，然后刪除下一個節點。但是如果節點是尾節點時，該方法就行不通了。
代碼如下：
// 在 O(1) 時間從無頭單鏈表中刪除節點
public void deleteNode(ListNode node){
// 不能為空，不能為尾節點
if (null == node || null == node.next) {
return;
}
node.val = node.next.val;
node.next = node.next.next;
}
2. 逆轉單鏈表
LeetCode 206. Reverse Linked List
題目描述：輸出一個單鏈表的逆序反轉后的鏈表。
分析：非遞歸的算法很簡單，用三個臨時指針 prev、cur、next 在鏈表上循環一遍即可。遞歸算法是先逆轉下一個節點，再逆轉當前節點。
下面是兩種算法的代碼：
// 逆轉單鏈表，循環方法
public ListNode reverseByLoop(ListNode head){
if (null == head || null == head.next) {
return head;
}
ListNode prev = null;
ListNode next = null;
// 用 head 作為 cur 指針
while (null != head) {
next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
// 逆轉單鏈表，遞歸方法
public ListNode reverseByRecursion(ListNode head){
// 第一個條件判斷異常，第二個條件是結束遞歸
if (null == head || null == head.next) {
return head;
}
ListNode newHead = reverseByRecursion(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
3. 刪除單鏈表倒數第 n 個節點
LeetCode 19. Remove Nth Node From End of List
題目描述：刪除單鏈表倒數第 n 個節點，1 <= n <= length，盡量在一次遍歷中完成。
分析：看到題目時的第一想法是先遍歷一次計算出單鏈表的長度 length，然后在遍歷第二次刪除第 length - n + 1 個節點，但是這需要遍歷兩次。正常的刪除第 n 個節點只需要遍歷一次就可以，如何只遍歷一次找到倒數第 n 個節點呢？可以設置兩個指針 p1、p2，首先 p1 和 p2 都指向 head，p2 移動到第 n 個節點，然后 p1 和 p2 同時向后移動，當 p2 移動到末尾時，p1 剛好指向倒數第 n 個節點。因為最后要刪除倒數第 n 個節點，所以可以找到倒數第 n + 1 個節點，方便刪除節點。
代碼如下：
// 遍歷一次，刪除單鏈表倒數第 n 個節點
public ListNode removeNthFromEnd(ListNode head,int n){
if (null == head) {
return head;
}
ListNode p1 = head;
ListNode p2 = head;
// 1. p2 移動到第 n + 1 個節點
for (int i = 0; i < n; i ++>) {
p2 = p2.next;
}
// n == 鏈表長度時，p2 指向第 n + 1 節點為空，倒數第 n 個節點就是頭節點
if (null == p2) {
p1 = head.next;
return p1;
}
// p1 和 p2 同時向后移動，直到 p2 到達尾節點
while (null != p2.next) {
p1 = p1.next;
p2 = p2.next;
}
// 此時 p1 指向倒數第 n + 1 個節點，刪除它的下一個節點
p1.next = p1.next.next;
return head;
}
4. 求單鏈表的中間節點
題目描述：求單鏈表的中間節點，如果鏈表的長度為偶數，返回中間兩個節點的任意一個，若為奇數，則返回中間節點。
分析：這道題的思路和第 3 題「刪除單鏈表倒數第 n 個節點」很相似。如果要求只能遍歷一遍鏈表的花，也通過兩個指針來完成。兩個指針從頭節點開始，慢指針每次向后移動一步，快指針每次向后移動兩步，直到快指針移動到尾節點時，慢指針移動到中間節點。
// 遍歷一次，找出單鏈表的中間節點
public ListNode findMiddleNode(ListNode head){
if (null == head) {
return;
}
ListNode slow = head;
ListNode fast = head;
//如果要求在單鏈表長度為偶數的情況下，返回中間兩個節點的第一個，可以用下面的循環條件
//while(null != fast.next && null != fast.next.next)
while (null != fast && null != fast.next) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
5. 判斷單鏈表是否存在環
LeetCode 141. Linked List Cycle
題目描述：判斷一個單鏈表是否有環
分析：還是通過快慢指針來解決，兩個指針從頭節點開始，慢指針每次向后移動一步，快指針每次向后移動兩步，如果存在環，那么兩個指針一定會在環內相遇。
代碼如下：
// 判斷單鏈表是否有環
public boolean hasCycle(ListNode head){
if (null == head) {
return false;
}
ListNode slow = head;
ListNode fast = head;
while (null != fast.next && null != fast.next.next) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
return true;
}
}
return false;
}
6. 單鏈表是否有環擴展：找到環的入口點
LeetCode 142. Linked List Cycle II
題目描述：判斷單鏈表是否有環，如果有，找到環的入口點
分析：由上題可知，按照 p2 每次兩步，p1 每次一步的方式走，發現 p2 和 p1 重合，確定了單向鏈表有環路了。接下來，讓 p2 回到鏈表的頭部，重新走，每次步長不是走 2 了，而是走 1，那么當 p1 和 p2 再次相遇的時候，就是在環路的入口點。
假設起點到環入口的距離尾 a，p1 和 p2 第一次相遇的相交點 M 與環入口的距離為 b，環的周長為 L，當 p1 和 p2 第一次相遇時，假設 p1 走了 n 步。其中 p1 和 p2 第一次相遇時，p1 在環內走過的步數為 b，因為當 p1 走到環入口時，p2 已經在環內了，假設此時 p2 走到環入口的步數為 c，那么 p1 再走 c 步 p2 剛好追上來和 p1 相遇，c < L，所以此時 p1 肯定還沒走完一圈。那么根據上面的假設，有下面的關系：
p1 走的路徑： a + b = n
p2 走的路徑： a + b + k * L = 2n ，假設此時 p2 比 p1 多走了 k 圈環路，k >= 1
根據上面的兩個等式可以得出 k * L = n = a + b ，那么從相交點 M 開始，p1 再走 a（a = k * L - b） 步，就相當于走了 k 圈，然后回退 b 步，注意環入口到相交點的距離剛好為 b，所以 p1 再走 a 步時到達環入口；而 p2 從頭開始走 a 的話也到達了環入口，與 p1 相遇。
而在后面這個步驟中，p1 和 p2 前 a 步走的路徑不同，再次相遇時必然在環的入口點。
代碼如下：
// 找到環的入口點
public ListNode findLoopPort(ListNode head){
if (null == head) {
return null;
}
ListNode p1 = head;
ListNode p2 = head;
boolean hasCycle = false;
// 1. 判斷是否有環
while (null != p2.next && null != p2.next.next) {
p1 = p1.next;
p2 = p2.next.next;
if (p1 == p2) {
hasCycle = true;
break;
}
}
if (!hasCycle) {
return null;
}
// p2 從頭開始走，步長變為 1
p2 = head;
while (p1 != p2) {
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
7. 判斷兩個無環單鏈表是否相交
題目描述：給出兩個無環單鏈表
A: a1 → a2
↘
c1 → c2 → c3 → null
↗
B: b1 → b2 → b3
判斷 A 和 B 是否相交。
分析：
1.最直接的方法是判斷 A 鏈表的每個節點是否在 B 鏈表中，但是這種方法的時間復雜度為 O(Length(A) * Length(B))。
2.轉化為環的問題。把 B 鏈表接在 A 鏈表后面，如果得到的鏈表有環，則說明兩個鏈表相交。可以之前討論過的快慢指針來判斷是否有環，但是這里還有更簡單的方法。如果 B 鏈表和 A 鏈表相交，把 B 鏈表接在 A 鏈表后面時，B 鏈表的所有節點都在環內，所以此時只需要遍歷 B 鏈表，看是否會回到起點就可以判斷是否相交。這個方法需要先遍歷一次 A 鏈表，找到尾節點，然后還要遍歷一次 B 鏈表，判斷是否形成環，時間復雜度為 O(Length(A) + Length(B))。
3.除了轉化為環的問題，還可以利用“如果兩個鏈表相交于某一節點，那么之后的節點都是共有的”這個特點，如果兩個鏈表相交，那么最后一個節點一定是共有的。所以可以得出另外一種解法，先遍歷 A 鏈表，記住尾節點，然后遍歷 B 鏈表，比較兩個鏈表的尾節點，如果相同則相交，不同則不相交。時間復雜度為 O(Length(A) + Length(B))，空間復雜度為 O(1)，思路比解法 2 更簡單。
解法 3 的代碼如下：
// 判斷兩個無環單鏈表是否相交
public boolean isIntersect(ListNode headA, ListNode headB){
if (null == headA || null == headB) {
return false;
}
if (headA == headB) {
return true;
}
while (null != headA.next) {
headA = headA.next;
}
while (null != headB.next) {
headB = headB.next;
}
return headA == headB;
}
8. 兩個鏈表相交擴展：判斷兩個有環單鏈表是否相交
題目描述：上面的問題是針對無環鏈表的，如果是鏈表有環呢？
分析：如果兩個有環單鏈表相交，那么它們一定共有一個環。因此可以先用之前快慢指針的方式找到兩個鏈表中位于環內的兩個節點，如果相交的話，兩個節點在一個環內，那么移動其中一個節點，在一次循環內肯定可以與另外一個節點相遇。
代碼如下：
// 判斷兩個有環單鏈表是否相交
public boolean isisIntersectWithLoop(ListNode headA, ListNode headB){
if (null == headA || null == headB) {
return false;
}
if (headA == headB) {
return true;
}
headA = hasCycle(headA);
headB = hasCycle(headB);
// 沒有環，則退出
if (null == headA || headB) {
return false;
}
ListNode p = headB.next;
// p 在環內循環一次，直到與 headA 相遇
while (p != headB) {
if (p == headA) {
return true;
}
p = p.next;
}
return false;
}
// 判斷單鏈表是否有環，并返回環內的某一節點
public ListNode hasCycle(ListNode head){
if (null == head) {
return null;
}
ListNode slow = head;
ListNode fast = head;
while (null != fast.next && null != fast.next.next) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
return slow;
}
}
return null;
}
9. 兩個鏈表相交擴展：求兩個無環單鏈表的第一個相交點
LeetCode 160. Intersection of Two Linked Lists
題目描述：找到兩個無環單鏈表第一個相交點，如果不相交返回空，要求在線性時間復雜度和常量空間復雜度內完成。
分析：
下面所說的對齊：表示指針到鏈表末尾的距離相同。
1.分為先判斷是否有環，再求第一個相交點的方式。分別遍歷 A 鏈表和 B 鏈表，判斷它們的最后一個節點是否相交。然后利用對齊的思想，計算兩個鏈表的長度（這個可以放在之前的遍歷中做），分別用 p1 和 p2 指向兩個鏈表的頭，然后將較長鏈表的 p1 (假設為 p1)向后移動 LB - LA 個節點。這樣 p1 和 p2 對齊了，然后同時向后移動 p1 和 p2，直到 p1 == p2 ，相遇的點就是第一個節點。
2.解法 1 中為了對齊需要計算鏈表的長度，有沒有什么方法可以不用計算鏈表長度呢？假設 A 鏈表和 B 鏈表的長度為 LA 和 LB，假設 LB >= LA，兩個指針 p1 和 p2 分別指向 A 鏈表和 B 鏈表的頭節點。同時向后移動，當 p1 移動 A 鏈表的末尾時，p2 距離 B 鏈表的末尾的距離為 LB - LA ，此時可以看出我們已經得到了長度差，如何利用這個長度差對齊呢。這時將 p1 移動到 B 鏈表的頭部，兩個指針繼續移動，當 p2 移動到 B 鏈表的末尾時，p1 剛好移動了 LB - LA 步。此時再將 p2 移動到 A 鏈表的頭部，這樣 p1 和 p2 就對齊了，然后繼續移動，直到 p1 == p2 。如果兩個鏈表不相交，p1 和 p2 移動會同時移動到末尾都指向空，而相交的話，第一次相等時就是第一個相交點。這種方法的時間復雜度為 O (2 * (Length(B)))，最多要遍歷兩次長度較長的鏈表。
解法 2 的代碼如下：
// 求兩個無環單鏈表的第一個相交點
public ListNode getIntersectionNode(ListNode headA, ListNode headB){
if (null == headA || null == headB) {
return null;
}
if (headA == headB) {
return headA;
}
ListNode p1 = headA;
ListNode p2 = headB;
while (p1 != p2) {
// 遍歷完所在鏈表后從另外一個鏈表再開始
// 當 p1 和 p2 都換到另一個鏈表時，它們對齊了：
// （1）如果鏈表相交，p1 == p2 時為第一個相交點
// （2）如果鏈表不相交，p1 和 p2 同時移動到末尾，p1 = p2 = null，然后退出循環
p1 = (null == p1) ? headB : p1.next;
p2 = (null == p2) ? headA : p2.next;
}
return p1;
}
來自：http://johnnyshieh.me/posts/interview-linked-list/