代碼随想錄算法訓練營Day4|24.兩兩交換連結清單中的節點、19.删除連結清單的倒數第N個結點、160.連結清單相交、142.環形連結清單II

一、24 兩兩交換連結清單中的節點

1. 題目連結：https://leetcode.cn/problems/swap-nodes-in-pairs/

1. 思路：加入虛拟頭結點，然後cur指針每次移動兩格，将前後兩個節點交換。很簡單。時間複雜度O(n)。

1. 代碼：

var swapPairs = function(head) {
    if (!head) {
        return head;
    }
    var preHead = new ListNode(-1, head);
    var cur = preHead;
    while (cur.next && cur.next.next) {
        var left = cur.next;
        var right = cur.next.next;
        var temp = right.next;
        cur.next = right;
        right.next = left;
        left.next = temp;
        cur = cur.next.next;
    }
    return preHead.next;
};
           

二、19 删除連結清單的倒數第N個結點

1. 題目連結：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

1. 思路：一開始想到的是先算一下一共有幾個節點，然後再重新從頭開始周遊，這是兩趟掃描；第二種方法想到的是借助一個數組，将所有的周遊節點存進去，然後取出對應的哪一個節點資料；卡哥的算法思路是快慢指針法，讓fast先走n+1步，然後再讓slow和fast一起走，這樣fast走到末尾時slow就在倒數第n個節點上了。

1. 思路1代碼：

var removeNthFromEnd = function(head, n) {
    var preHead = new ListNode(-1, head);
    var len = 0;
    var cur = preHead;
    while (cur.next) {
        len += 1;
        cur = cur.next;
    }
    var result = len - n;
    var pointer = preHead;
    for (result; result>0; result--) {
        pointer = pointer.next;
    }
    if (pointer.next) {
        pointer.next = pointer.next.next;
    }
    else {
        pointer.next = null;
    }
    return preHead.next;
};
           

1. 思路2代碼：

var removeNthFromEnd = function(head, n) {
    var preHead = new ListNode(-1, head);
    var stack = [];
    var cur = preHead;
    while (cur) {
        stack.push(cur);
        cur = cur.next;
    }
    var node = stack[stack.length - n - 1];
    if (node.next) {
        node.next = node.next.next;
    }
    else {
        node.next = null;
    }
    return preHead.next;
};
           

1. 卡哥思路代碼：

var removeNthFromEnd = function(head, n) {
    var preHead = new ListNode(-1, head);
    var fast = preHead;
    var slow = preHead;
    // 此處循環為n+1，是為了友善slow停在删除節點的前一個節點上
    for (let i = n+1; i > 0; i--) {
        fast = fast.next;
    }
    while (fast) {
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next ? slow.next.next : null;
    return preHead.next;
};
           

三、160 連結清單相交

1. 題目連結：https://leetcode.cn/problems/intersection-of-two-linked-lists/

1. 思路：首先想到的是借助棧來做，将兩個連結清單分别壓入兩個棧中，然後出棧，依次比較，直至不相同的地方，時間複雜度O(3m/2+3n/2)，空間複雜度O(m+n)，這種就不寫了；其次還想到一種遞歸的方式，首先需要判斷一個連結清單是否是另一個連結清單的子連結清單，如果是的話傳回這一個連結清單，而如果不是的話遞歸這個連結清單的next和另外那個連結清單，不過可見時間複雜度會較高。但是題目要求時間複雜度O(m+n)、空間複雜度O(1)，卡哥的方式是求出兩個連結清單的長度，以及其內插補點，然後讓curA移動到兩個連結清單的尾部對齊的部位，再依次前進，直至相等。

1. 遞歸代碼：（未解決）

var getIntersectionNode = function(headA, headB) {
    if (isSonLink(headA, headB)) {
        return headA;
    }
    else {
        getIntersectionNode(headA.next, headB);
    }
};

// 求A是否為B的子連結清單
var isSonLink = function(A, B) {
    var cur = B;
    // 空指針是所有指針的子連結清單
    if (!A) {
        return true;
    }
    // B周遊到末尾，判斷是否有一個指針會等于A
    while (cur) {
        if (cur === A) {
            return true;
        }
        cur = cur.next;
    }
    return false;
}
           

1. 卡哥思路：

var getIntersectionNode = function(headA, headB) {
    var curA = headA;
    var curB = headB;
    var lenA = 0;
    var lenB = 0;
    while (curA) {
        lenA += 1;
        curA = curA.next;
    }
    while (curB) {
        lenB += 1;
        curB = curB.next;
    }
    curA = headA;
    curB = headB;
    if (lenA >= lenB) {
        for (let i=lenA-lenB; i>0; i--) {
            curA = curA.next;
        }
    }
    else {
        for (let i=lenB-lenA; i>0; i--) {
            curB = curB.next;
        }  
    }
    while (curA && curB) {
        if (curA == curB) {
            return curA;
        }
        curA = curA.next;
        curB = curB.next;
    }
    return null;
};
           

1. 代碼随想錄：（還是有很多可以精簡的地方）

var getListLen = function(head) {
    let len = 0, cur = head;
    while(cur) {
       len++;
       cur = cur.next;
    }
    return len;
}
var getIntersectionNode = function(headA, headB) {
    let curA = headA,curB = headB,
        lenA = getListLen(headA),   // 求連結清單A的長度
        lenB = getListLen(headB);  
    if(lenA < lenB) {       // 讓curA為最長連結清單的頭，lenA為其長度
    
        // 交換變量注意加 “分号” ，兩個數組交換變量在同一個作用域下時
        // 如果不加分号，下面兩條代碼等同于一條代碼: [curA, curB] = [lenB, lenA]
        
        [curA, curB] = [curB, curA];
        [lenA, lenB] = [lenB, lenA];
    }
    let i = lenA - lenB;   // 求長度差
    while(i-- > 0) {       // 讓curA和curB在同一起點上（末尾位置對齊）
        curA = curA.next;
    }
    while(curA && curA !== curB) {  // 周遊curA 和 curB，遇到相同則直接傳回
        curA = curA.next;
        curB = curB.next;
    }
    return curA;
};
           

四、142 環形連結清單II

1. 題目連結：https://leetcode.cn/problems/linked-list-cycle-ii/

1. 思路：這道題真是幾遍都記不住，直接看提示吧。。。

1. 文章連結：https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html

1. 代碼：

var detectCycle = function(head) {
    // 快指針每次走兩步，慢指針每次走一步
    var slow = head, fast = head;
    while (fast && fast.next) {
        fast = fast.next.next;
        slow = slow.next;
        // 快慢指針相遇
        if (fast == slow) {
            // 從相遇點和頭部分别走，他倆相遇了就一定是環的入口
            var index1 = fast;
            var index2 = head;
            while (index1 != index2) {
                index1 = index1.next;
                index2 = index2.next;
            }
            return index1;
        }
    }
    return null;
};
           

今日學習時間：2h左右

總結：今天前兩道題做的還是比較順利的，但後兩道題相對來講比較難，不過我認為這兩道題的泛用度也沒有那麼高，都是針對連結清單的特殊處理，是以沒有太過深入研究，特别是142，除了記住我感覺别無他法。。。連結清單相交我用了一種遞歸的方式，但還沒有看出問題在哪。下次再看的時候再來記一下142題。