算法 | 第2章連結清單相關《程式員面試金典》

前言
0. *經驗總結
- 0.1 程式員面試金典 P79
- 0.2 需要詢問面試官的點
- 0.3 快慢指針
- 0.4 遞歸
1. 移除重複節點 [easy]
- 1.1 考慮點
- 1.2 解法
  - 1.2.1 集合法
  - 1.2.2 兩循環法
2. 傳回倒數第 k 個節點 [easy]
- 2.1 考慮點
- 2.2 解法
  - 2.2.1 雙指針同步運動法（快慢指針）（優）
  - 2.2.2 使用棧法
  - 2.2.3 遞歸
3. 删除中間節點 [easy]
- 3.1 考慮點
- 3.2 解法
  - 3.2.1 複制自己法
4. 分割連結清單 [medium]
- 4.1 考慮點
- 4.2 解法
  - 4.2.1 雙指針逐個處理法
  - 4.2.2 排序法
  - 4.2.3 頭插法
  - 4.2.4 原地删除
5. 連結清單求和 [medium]
- 5.1 考慮點
- 5.2 解法
  - 5.2.1 反向存放法
  - 5.2.2 遞歸法
6. 回文連結清單 [easy]
- 6.1 考慮點
- 6.2 解法
  - 6.2.1 改變方向雙向周遊法（優）
  - 6.2.2 将值複制到數組中後用雙指針法
  - 6.2.3 遞歸
7. 連結清單相交 [easy]
- 7.1 考慮點
- 7.2 解法
  - 7.2.1 長度對齊雙指針法
  - 7.2.2 雙指針（優）
8. 環路檢測 [medium]
- 8.1 考慮點
- 8.2 解法
  - 8.2.1 快慢指針法（優）
  - 8.2.2 哈希表
最後

本系列筆記主要記錄筆者刷《程式員面試金典》算法的一些想法與經驗總結，按專題分類，主要由兩部分構成：經驗值點和經典題目。其中重點放在經典題目上；

連結清單的特點：無法在常數時間複雜度内通路連結清單的特定元素；可以在參數事件複雜度内加入和删除元素；
如果連結清單被多個對象引用，當連結清單頭結點變了，可能會有一些對象仍然指向原頭結點；解決方法：可以用LinkedList封裝Node類，該類隻包含一個成員變量：頭結點；
連結清單問題可以關注“快慢指針”和遞歸；

是否可以修改原連結清單；
是否可以開辟額外空間；
時間優先還是空間優先；
在面試中要弄清單向連結清單和雙向連結清單；

快慢指針又稱雙指針，是一個廣泛的概念，隻要涉及兩個指針周遊連結清單，并且一前一後，都可以稱為快慢指針；
快慢指針在不同題目有不同的作用，常見類型有：
- 找到中點：慢指針每走n步時，快指針走2n步，當快指針達到尾部時；
- 找到三分之一點：慢指針走n步，快指針走3n步；
- 找到倒數第x個節點：快指針先走x步後，慢指針從頭出發，與快指針速度一樣，當快指針達到尾部時，慢指針到倒數第k個節點；【詳情見 2. 傳回倒數第 k 個節點】
- 測試環形連結清單：慢指針每走n步時，快指針走2n步，能相遇說明環形；
- 測試連結清單是否成環并找到第一個成環節點：【詳情見 8. 環路檢測】
- ……

實際上所有遞歸算法都可以轉換成疊代法，隻是後者可能要複雜得多；
一般來說，遞歸解法更簡潔，但效率低下；

需要問清楚面試官是否可以開辟額外空間；
需要詢問面試官時間優先還是空間優先；

public ListNode removeDuplicateNodes(ListNode head) {
    if(head == null || head.next == null){
        return head;
    }
    ListNode cur = head;
    ListNode index = head;
    Set<Integer> set = new HashSet<>();
    set.add(head.val);
    while( cur.next != null){
		cur = cur.next;
        if( !set.contains(cur.val) ){
			index.next = cur;
            index = cur;
            set.add(cur.val);
        } else {
            index.next = null;
        }
    } 
    return head;
}

執行時間：66.09%；記憶體消耗：51.20%；
也可以用哈希表；
時間複雜度：O(N)，其中 N 是給定連結清單中節點的數目；
空間複雜度：O(N)。在最壞情況下，給定連結清單中每個節點都不相同，哈希表中需要存儲所有的 N個值；

public ListNode removeDuplicateNodes(ListNode head) {
    ListNode ob = head;
    while (ob != null) {
        ListNode oc = ob;
        while (oc.next != null) {
            if (oc.next.val == ob.val) {
                oc.next = oc.next.next;
            } else {
                oc = oc.next;
            }
        }
        ob = ob.next;
    }
    return head;
}

執行時間：93.52%；記憶體消耗：93.52%；
時間複雜度：O(N2)，其中 N 是給定連結清單中節點的數目；
空間複雜度：O(1)；

public int kthToLast(ListNode head, int k) {
    if(head == null || head.next == null){
        return head.val;
    }
    ListNode cur = head;
    ListNode index = head;
    //cur先走k-1個步長
    for(int i = 0; i < k - 1; i++ ){
        cur = cur.next;
    }
    //index上連結清單，跟cur同步運動，當cur到達連結清單尾時，cur為倒數第k個
    while(cur.next != null){
        cur = cur.next;
        index = index.next;
    }
    return index.val;
}

執行時間：100.00%；記憶體消耗：30.78%；
第一個指針先移動k步，然後第二個指針再從頭開始，這個時候這兩個指針同時移動，當第一個指針到連結清單的末尾的時候，傳回第二個指針即可；

public int kthToLast(ListNode head, int k) {
    Stack<ListNode> stack = new Stack<>();
    //連結清單節點壓棧
    while (head != null) {
        stack.push(head);
        head = head.next;
    }
    //在出棧串成新的連結清單
    ListNode firstNode = stack.pop();
    while (--k > 0) {
        ListNode temp = stack.pop();
        temp.next = firstNode;
        firstNode = temp;
    }
    return firstNode.val;
}

執行時間：9.00%；記憶體消耗：58.84%；
把原連結清單的結點全部壓棧，然後再把棧中最上面的k個節點出棧，出棧的結點重新串成一個新的連結清單即可；

int size;
public int kthToLast(ListNode head, int k) {
    if (head == null){
    	return 0;
    }
    int value = kthToLast(head.next, k);
    if (++size == k){
        return head.val;
    }
    return value;
}

執行時間：100.00%；記憶體消耗：24.44%；
遞歸通路整個連結清單，到達尾部時，回傳一個設定為0的size計數器，後續調用每次都會将計數器加1，當計數器為k是，即為倒數第k個。value為暫存的結果值；

題目有點“腦筋急轉彎”的意思，注意給出的是目前要删除的節點；
面試官期待的是：當待删除的節點為連結清單尾節點時的情況：
- 因為不能通路前一個節點，要從其他方面考慮解決方法；
- 可以考慮将該節點标記為假節點，即實體上存在，邏輯上不在；

public void deleteNode(ListNode node) {
    if(node == null || node.next == null){
        return;
    }
    ListNode nextNode = node.next;
    node.val = nextNode.val;
    node.next = nextNode.next;
}

執行時間：100.00%；記憶體消耗：72.05%；
如果隻能通路目前節點，那麼該題的解題思路就是，将自己變成其他節點；
- 舉個例子：A->B->C->D；
- 如果要删掉 B 節點，那麼隻需要将 B 變為 C，再把 B 的指針指向 D，即可完成；

注意題目意思，可以排序，但不一定是排序；
如果本題描述的是數組，對于如何移動元素要謹慎，數組元素的移動通常開銷很大。但連結清單相對比較簡單；

public ListNode partition(ListNode head, int x) {
    if(head == null || head.next == null ){
        return head;
    }
    //找到比x小的節點，該節點離x節點最近
    ListNode index = head;
    while(index.val < x && index.next != null){
        index = index.next;
    }
    //用2個指針完成移位操作
    //index為首個大于等于x的節點
    //cur為index2的next
    ListNode cur = index.next;
    while(index.next != null){
        if(cur.val >= x){
            //繼續
            index = index.next;
            cur = cur.next;
        } else {
            //移位
            index.next = cur.next;
            if( head.val < x){
				cur.next = head.next;
                head.next = cur;
            } else {
                cur.next = head;
                head = cur;
            }
            cur = index.next;
        }
    }
    return head;
}

執行時間：100.00%；記憶體消耗：64.81%；

public ListNode partition(ListNode head, int x) {
    return sortList(head, null);
}

private ListNode sortList(ListNode head, ListNode tail) {
    //無法繼續拆分的情況
    if (head == null) {
        return null;
    }
    //無法繼續拆分的情況
    if (head.next == tail) {
        head.next = null;
        return head;
    }
    //快慢指針找到中間節點
    ListNode slow = head, fast = head;
    while (fast != tail && fast.next != tail) {
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode mid = slow;
    //左邊繼續拆分
    ListNode left = sortList(head, mid);
    //右邊繼續拆分
    ListNode right = sortList(mid, tail);
    //有序連結清單合并
    return merge(left, right);
}

private ListNode merge(ListNode left, ListNode right) {
    ListNode mergeNode = new ListNode();
    ListNode help = mergeNode;
    //比較兩個連結清單目前的值，值小的連結清單就把引用賦給mergeNode，并向後移動一位重新指派給自己，同時help指向值小的那個節點
    while (left != null && right != null) {
        if (left.val < right.val) {
            help.next = left;
            left = left.next;
        } else {
            help.next = right;
            right = right.next;
        }
        help = help.next;
    }
    //最後如果有剩餘的節點，就一次性鍊上去 
    help.next = left == null ? right : left;
    return mergeNode.next;
}

執行時間：100.00%；記憶體消耗：83.65%；
最無腦的做法是排序，這題不管x給什麼，隻需要對連結清單進行一次排序，既能滿足題目要求，之前的題目中有練習過插入排序、歸并排序，随便哪一種都可以，當然歸并的效率更高一點；

public ListNode partition(ListNode head, int x) {
    ListNode dummy = new ListNode();
    dummy.next = head;
    while (head != null && head.next != null) {
        int nextVal = head.next.val;
        if (nextVal < x) {
            ListNode next = head.next;
            head.next = head.next.next;
            next.next = dummy.next;
            dummy.next = next;
        } else {
            head = head.next;
        }
    }
    return dummy.next;
}

執行時間：100.00%；記憶體消耗：20.44%；
逐個周遊，遇到小于x值的節點，就插到頭部；
PS：Java中HashMap，jdk1.8之前，擴容時連結清單采用的就是頭插法（存在死循環的問題，1.8改了）；

public ListNode partition(ListNode head, int x) {
    ListNode dummy = new ListNode();
    dummy.next = head;
    ListNode smallDummy = new ListNode();
    ListNode small = smallDummy;
    //和删除節點的套路一樣，先處理頭節點滿足條件的情況
    while (head != null) {
        if (head.val >= x) {
            break;
        }
        small.next = new ListNode(head.val);
        small = small.next;
        head = head.next;
    }
    //删除
    ListNode cur = head;
    ListNode pre = null;
    while (cur != null) {
        if (cur.val < x) {
            pre.next = cur.next;
            small.next = new ListNode(cur.val);
            small = small.next;
        } else {
            pre = cur;
        }
        cur = cur.next;
    }
    small.next = head;
    return smallDummy.next;
}

執行時間：100.00%；記憶體消耗：56.22%；
按照删除節點的方式，遇到小于x值的節點，就從原連結清單中删除，并添加到新的連結清單中，這樣一次周遊結束後，隻要把新的連結清單連上原連結清單即可；

需要考慮連結清單長度不一導緻的空指針異常問題；
進階的思考：
- 連結清單長度不一時的對位問題，如（1 -> 2 -> 3 -> 4）和（5 -> 6 -> 7），這裡5對2而不是1；
- 上述問題可以周遊連結清單，用0占位解決；

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    if( l1 == null && l2 == null){
        return null;
    }
    ListNode cur1 = l1;
    ListNode cur2 = l2;
    int cache = 0;
    boolean isFirst = true;
    ListNode head = null;
    ListNode index = null;
    while( cur1 != null || cur2 != null){
        //加法
        int value = 0;
        if( cur1 == null){
            value = cur2.val + cache;
            cur2 = cur2.next;
        } else if ( cur2 == null){
            value = cur1.val + cache;
            cur1 = cur1.next;
        } else {
            value = cur1.val + cur2.val + cache;
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        //進位在cache儲存
        cache = value / 10;
        //構造新節點，新節點指向新節點
        ListNode node = new ListNode(value%10);
        if(isFirst){
            head = node;
            index = node;
            isFirst = false;
        } else {
            index.next = node;
            index = node;
        }
    }
    //判斷cache
    if(cache != 0){
        ListNode node = new ListNode(cache);
        index.next = node;
    }
    return head;
}

執行時間：97.51%；記憶體消耗：33.72%；
通常做法：逐個周遊，進位，建構新節點；

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode head = new ListNode(0);
    helper(head, l1, l2, 0);
    return head.next;
}
private void helper(ListNode result, ListNode l1, ListNode l2, int carry) {
    if (l1 == null && l2 == null && carry == 0){
        return;
    }
    int sum = (l1 != null ? l1.val : 0) + (l2 != null ? l2.val : 0) + carry;
    result.next = new ListNode(0);
    result.next.val = sum % 10;
    carry = sum / 10;
    helper(result.next, l1 != null ? l1.next : null, l2 != null ? l2.next : null, carry);
}

執行時間：100.00%；記憶體消耗：26.25%；

對于連結清單，可以思考的角度有：改變連結清單方向、拼接、成環等；
需要問清楚面試官是否可以修改連結清單；

public boolean isPalindrome(ListNode head) {
    if(head == null){
        return true;
    }
    //統計連結清單長度
    ListNode cur = head;
    int count = 0;
    while( cur != null ){
        count++;
        cur = cur.next;
    }
    if( count < 2){
        return true;
    }
    //改變前 count/2-1 個節點指向，分奇偶讨論
    ListNode right = head;
        //定位right指針
    if( count % 2 == 1 ){
        //奇數情況
        for( int i = 0; i < count/2+1; i++){
            right = right.next;
        }
    } else {
        //偶數情況
        for( int i = 0; i < count/2; i++){
            right = right.next;
        }
    }
    //改變前count/2-1個節點方向
    ListNode left = head;
    cur = head.next;
    ListNode mid = cur.next;
    //判斷對隻有2~3個節點單獨判斷
    if(count < 4){
        return left.val == right.val;
    }
    for( int i = 0; i < count/2-1; i++){
        cur.next = left;
        left = cur;
        cur = mid;
        mid = mid.next;
    }
    //周遊比較left和right
    while(right != null){
        if(left.val != right.val){
            return false;
        }
        right = right.next;
        left = left.next;
    }
    return true;
}

執行時間：96.85%；記憶體消耗：80.19%；
不使用額外空間；
需要注意，是否可以改變原連結清單；

public boolean isPalindrome(ListNode head) {
    List<Integer> vals = new ArrayList<Integer>();
    // 将連結清單的值複制到數組中
    ListNode currentNode = head;
    while (currentNode != null) {
        vals.add(currentNode.val);
        currentNode = currentNode.next;
    }
    // 使用雙指針判斷是否回文
    int front = 0;
    int back = vals.size() - 1;
    while (front < back) {
        if (!vals.get(front).equals(vals.get(back))) {
            return false;
        }
        front++;
        back--;
    }
    return true;
}

執行時間：32.69%；記憶體消耗：24.77%；
時間複雜度：O(n)，其中 n 指的是連結清單的元素個數；
- 第一步：周遊連結清單并将值複制到數組中，O(n)。
- 第二步：雙指針判斷是否為回文，執行了 O(n/2) 次的判斷，即 O(n)。
- 總的時間複雜度：O(2n) = O(n)。
空間複雜度：O(n)，其中 n 指的是連結清單的元素個數，我們使用了一個數組清單存放連結清單的元素值；
需要開辟額外空間；

private ListNode frontPointer;
private boolean recursivelyCheck(ListNode currentNode) {
    if (currentNode != null) {
        if (!recursivelyCheck(currentNode.next)) {
            return false;
        }
        if (currentNode.val != frontPointer.val) {
            return false;
        }
        frontPointer = frontPointer.next;
    }
    return true;
}
public boolean isPalindrome(ListNode head) {
    frontPointer = head;
    return recursivelyCheck(head);
}

執行時間：56.10%；記憶體消耗：5.05%；
時間複雜度：O(n)，其中 n 指的是連結清單的大小；
空間複雜度：O(n)，其中 n 指的是連結清單的大小。這種方法不僅使用了 O(n)的空間，且比第一種方法更差，因為在許多語言中，堆棧幀的開銷很大（如 Python），并且最大的運作時堆棧深度為 1000（可以增加，但是有可能導緻底層解釋程式記憶體出錯）。為每個節點建立堆棧幀極大的限制了算法能夠處理的最大連結清單大小；

這裡不能使用連結清單反轉，題目要求不能破壞原有結構；
對于兩條長度不同的連結清單而言，可以先周遊求出各自的長度再做計算，也可以使用；兩個指針走完兩條連結清單，最後必然能重合，因為指針的速度（步長）的一樣的；

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if( headA == null || headB == null ){
        return null;
    }
    ListNode cur = headA;
    int countA = 0;
    while( cur != null ){
        countA++;
        cur = cur.next;
    }
    cur = headB;
    int countB = 0;
    while( cur != null){
        countB++;
        cur = cur.next;
    }
    //保證headA長于headB
    if( countA < countB){
        return getIntersectionNode(headB,headA);
    }
    ListNode curA = headA;
    ListNode curB = headB;
    for( int i = 0; i < countA-countB; i++){
        curA = curA.next;
    }
    while( curA != null ){
        if( curA.equals(curB) ){
            return curA;
        }
        curA = curA.next;
        curB = curB.next;
    }
    return null;
}

執行時間：100.00%；記憶體消耗：57.18%；
時間複雜度：O(A+B)，A和B是兩個連結清單的長度；

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
     ListNode h1 = headA;
     ListNode h2 = headB;
     while(h1 != h2){
         h1 = (h1 == null ? headB : h1.next); 
         h2 = (h2 == null ? headA : h2.next); 
     }
     return h1;
}

對于h1來說，走到末尾（或相交點）時，走了兩段連結清單（兩段連結清單不同部分）的路徑；
對于h2來說，走到末尾（或相交點）時，走了兩段連結清單（兩段連結清單不同部分）的路徑；
h1和h2走過的路徑相同，是以第二輪就能比對到；

處理環形連結清單可以試試快慢指針；

public ListNode detectCycle(ListNode head) {
    if( head == null ){
        return null;
    }
    if(head.next == null){
        return null;
    }
    if(head.next.next == null){
        return null;
    }
    //使用快慢指針找到有count個環成圈;
    ListNode fast = head.next.next;
    ListNode slow = head.next;
    int count = 1; //count變量不是必要的
    while( fast != slow ){
        if(fast == null || slow == null){
            return null;
        }
        slow = slow.next;
        if(fast.next != null){
            fast = fast.next.next;
        } else {
            return null;
        }
        count++;
    }
    // cur 和 slow 一起走，走n步到環路開頭節點
    ListNode cur = head;
    while( cur != slow ){
        cur = cur.next;
        slow = slow.next;
    }
    return cur;
}

執行時間：100.00%；記憶體消耗：53.71%；
時間複雜度：O(n)，n為不成環的節點和成環節點的較大值；
空間複雜度：O(1)，不開辟額外空間，算法中的count不是必要的；
算法解釋：算法主要分為兩個部分，如下：
- 使用快慢指針找到有count個環成圈：走x步到達下标為x的節點。可以通過快慢指針獲得count（或count的質因數）個節點成圈，同時慢指針走了count步（此時快慢指針所指節點下标為count）。假設環路開頭節點的下标為 n（n<=count），從連結清單頭走要走n步到環路開頭節點；
- 走n步到環路開頭節點：從連結清單頭到快慢指針處走count步，從連結清單頭到環路開頭節點要n步。如果要從環路開頭節點走到快慢指針處要走count-n步；如果要從環路開頭節點再一次回到開頭節點必須走完一個圈（或n圈），即走count步。那麼從快慢指針處走到開頭節點至少就要count-(count-n)=n步，而我們從連結清單頭走到環路開頭節點也是要走n步；

public ListNode detectCycle(ListNode head) {
    ListNode pos = head;
    Set<ListNode> visited = new HashSet<ListNode>();
    while (pos != null) {
        if (visited.contains(pos)) {
            return pos;
        } else {
            visited.add(pos);
        }
        pos = pos.next;
    }
    return null;
}

執行時間：30.58%；記憶體消耗：24.80%；
時間複雜度：O(N)，其中 N 為連結清單中節點的數目。我們恰好需要通路連結清單中的每一個節點；
空間複雜度：O(N)，其中 N 為連結清單中節點的數目。我們需要将連結清單中的每個節點都儲存在哈希表當中；

新人制作，如有錯誤，歡迎指出，感激不盡！

歡迎關注公衆号，會分享一些更日常的東西！

如需轉載，請标注出處！

算法 | 第2章 連結清單相關《程式員面試金典》

算法 | 第2章連結清單相關《程式員面試金典》