24.兩兩交換鏈表中的節(jié)點(diǎn)

題目描述：

給你一個(gè)鏈表，兩兩交換其中相鄰的節(jié)點(diǎn)，并返回交換后鏈表的頭節(jié)點(diǎn)。你必須在不修改節(jié)點(diǎn)內(nèi)部的值的情況下完成本題（即，只能進(jìn)行節(jié)點(diǎn)交換）
示例 1：
輸入：head = [1,2,3,4]
輸出：[2,1,4,3]
示例 2：
輸入：head = []
輸出：[]
示例 3：
輸入：head = [1]
輸出：[1]

解題思路

舉例：[1,2,3,4] 利用虛擬頭節(jié)點(diǎn) -> [0,1,2,3,4]

image.png

var swapPairs = function(head) {
    let dymmic = new ListNode(0, head);
    let cur = dymmic;
    while(cur && cur.next && cur.next.next) {
        let pre = cur.next; // pre  = [1,2,3,4]
        cur.next = cur.next.next; // cur = [0,2,3,4]
        let next = cur.next.next; // next = [3,4]
        cur.next.next = pre; // cur = [0,2,1,2,3,4]
        pre.next = next; // pre = [1,3,4]
        cur = pre; // cur = [0,2,1,3,4]
    }
    return dymmic.next;
};

• 時(shí)間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(1)

19.刪除鏈表的倒數(shù)第 N 個(gè)結(jié)點(diǎn)

題目描述：

給你一個(gè)鏈表，刪除鏈表的倒數(shù)第 n 個(gè)結(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)。
輸入：head = [1,2,3,4,5], n = 2
輸出：[1,2,3,5]
示例 2：
輸入：head = [1], n = 1
輸出：[]
示例 3：
輸入：head = [1,2], n = 1
輸出：[1]

解題思路

• 利用快慢指針
• 快指針：先一步移動(dòng)n個(gè)步數(shù)
• 慢指針：等快指針到達(dá)n個(gè)步數(shù)后，快慢指針一同移動(dòng)，直到快指針的next為null，此時(shí)慢指針的指向即為倒數(shù)第N的節(jié)點(diǎn)

var removeNthFromEnd = function(head, n) {
    let dymmic = new ListNode(0, head);
    let fast = dymmic;
    let slow = dymmic;
    while(n--) {
        fast = fast.next
    }
    while(fast.next) {
        fast = fast.next
        slow = slow.next
    }
    slow.next = slow.next.next
    return dymmic.next;
};

• 時(shí)間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(1)

面試題 02.07. 鏈表相交

題目描述：

給你兩個(gè)單鏈表的頭節(jié)點(diǎn) headA 和 headB ，請(qǐng)你找出并返回兩個(gè)單鏈表相交的起始節(jié)點(diǎn)。如果兩個(gè)鏈表沒有交點(diǎn)，返回 null 。
圖示兩個(gè)鏈表在節(jié)點(diǎn) c1 開始相交：

image.png

題目數(shù)據(jù) 保證 整個(gè)鏈?zhǔn)浇Y(jié)構(gòu)中不存在環(huán)。
注意，函數(shù)返回結(jié)果后，鏈表必須 保持其原始結(jié)構(gòu) 。
示例1：

image.png

輸入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
輸出：Intersected at '8'
解釋：相交節(jié)點(diǎn)的值為 8 （注意，如果兩個(gè)鏈表相交則不能為 0）。
從各自的表頭開始算起，鏈表 A 為 [4,1,8,4,5]，鏈表 B 為 [5,0,1,8,4,5]。
在 A 中，相交節(jié)點(diǎn)前有 2 個(gè)節(jié)點(diǎn)；在 B 中，相交節(jié)點(diǎn)前有 3 個(gè)節(jié)點(diǎn)。
示例 2：

image.png

輸入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
輸出：Intersected at '2'
解釋：相交節(jié)點(diǎn)的值為 2 （注意，如果兩個(gè)鏈表相交則不能為 0）。
從各自的表頭開始算起，鏈表 A 為 [0,9,1,2,4]，鏈表 B 為 [3,2,4]。
在 A 中，相交節(jié)點(diǎn)前有 3 個(gè)節(jié)點(diǎn)；在 B 中，相交節(jié)點(diǎn)前有 1 個(gè)節(jié)點(diǎn)。
示例 3：

image.png

輸入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
輸出：null
解釋：從各自的表頭開始算起，鏈表 A 為 [2,6,4]，鏈表 B 為 [1,5]。
由于這兩個(gè)鏈表不相交，所以 intersectVal 必須為 0，而 skipA 和 skipB 可以是任意值。
這兩個(gè)鏈表不相交，因此返回 null 。

解題思路

• 首先計(jì)算 A,B 兩個(gè)鏈表分別的長(zhǎng)度
• 計(jì)算差值diffDep，讓長(zhǎng)鏈表首先移動(dòng)diffDep個(gè)步數(shù)
• 再讓A，B兩個(gè)鏈表同時(shí)移動(dòng)，直到找到相同的頭節(jié)點(diǎn)，返回即可
• 否則返回null

注意
1 判斷頭節(jié)點(diǎn)是否相等：比較的是節(jié)點(diǎn)指向而不是節(jié)點(diǎn)值

var getIntersectionNode = function(headA, headB) {
    let A = headA;
    let Alen = 0
    let B = headB;
    let Blen = 0;
    while(A) {
        A = A.next;
        Alen++
    }
    while(B) {
        B = B.next;
        Blen++
    }
    let diffDep = Math.abs(Alen - Blen)
    while (diffDep--) {
        if (Alen > Blen) {
            headA = headA.next
        } else {
            headB = headB.next
        }
    }
    while(headA) {
        if (headA === headB) {
            return headA
        } else {
            headA = headA.next
            headB = headB.next
        }
    }
    return null
};

• 時(shí)間復(fù)雜度：O(n+m)
• 空間復(fù)雜度：O(1)

142. 環(huán)形鏈表 II

題目描述：

給定一個(gè)鏈表的頭節(jié)點(diǎn) head ，返回鏈表開始入環(huán)的第一個(gè)節(jié)點(diǎn)。 如果鏈表無環(huán)，則返回 null。
如果鏈表中有某個(gè)節(jié)點(diǎn)，可以通過連續(xù)跟蹤 next 指針再次到達(dá)，則鏈表中存在環(huán)。
為了表示給定鏈表中的環(huán)，評(píng)測(cè)系統(tǒng)內(nèi)部使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。
如果 pos 是 -1，則在該鏈表中沒有環(huán)。注意：pos 不作為參數(shù)進(jìn)行傳遞，僅僅是為了標(biāo)識(shí)鏈表的實(shí)際情況。
不允許修改鏈表。
示例 1：

image.png

輸入：head = [3,2,0,-4], pos = 1
輸出：返回索引為 1 的鏈表節(jié)點(diǎn)
解釋：鏈表中有一個(gè)環(huán)，其尾部連接到第二個(gè)節(jié)點(diǎn)。
示例 2：

image.png

輸入：head = [1,2], pos = 0
輸出：返回索引為 0 的鏈表節(jié)點(diǎn)
解釋：鏈表中有一個(gè)環(huán)，其尾部連接到第一個(gè)節(jié)點(diǎn)。
示例 3：

image.png

輸入：head = [1], pos = -1
輸出：返回 null

解釋：鏈表中沒有環(huán)。

解題思路

• 判斷鏈表是否為環(huán)行鏈表
• 如果為環(huán)形鏈表，如何找到環(huán)形入口

如何判斷鏈表是否為環(huán)形
使用快慢指針法，分別設(shè)置fast和slow，從頭節(jié)點(diǎn)出發(fā)，fast一次移動(dòng)2個(gè)節(jié)點(diǎn)，slow一次移動(dòng)1個(gè)節(jié)點(diǎn)，如果途中相遇，則為環(huán)形鏈表。

如何找到環(huán)形入口
從頭節(jié)點(diǎn)出發(fā)1個(gè)指針，從相遇節(jié)點(diǎn)出發(fā)1個(gè)指針，這兩個(gè)指針每次同時(shí)只移動(dòng)1個(gè)節(jié)點(diǎn)，當(dāng)這兩個(gè)指針相遇的時(shí)候就是環(huán)形入口的節(jié)點(diǎn)。

var detectCycle = function(head) {
    if (!head || !head.next) {
        return null
    }
    let fast = head.next.next;
    let slow = head.next;
    while(fast && fast.next && fast !== slow) {
        slow = slow.next
        fast = fast.next.next
    }
    if (!fast || !fast.next) {
        return null
    }
    slow = head;
    while (slow !== fast) {
        slow = slow.next
        fast = fast.next
    }
    return slow;
};

環(huán)形鏈表推理請(qǐng)參考：代碼隨想錄
另外友友們，有沒有好用的畫圖軟件推薦呀