LeetCode#160-Intersection of Two Linked Lists-相交鏈表

2020 年 4 月 22 日
筆記
LeetCode刷題

一、題目

編寫一個程式，找到兩個單鏈表相交的起始節點。
如下面的兩個鏈表：

在節點 c1 開始相交。

示例 1:

輸入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
輸出：Reference of the node with value = 8
輸入解釋：相交節點的值為 8 （注意，如果兩個列表相交則不能為 0）。
從各自的表頭開始算起，鏈表 A 為 [4,1,8,4,5]，鏈表 B 為 [5,0,1,8,4,5]。
在 A 中，相交節點前有 2 個節點；在 B 中，相交節點前有 3 個節點。

示例 2:

輸入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
輸出：Reference of the node with value = 2
輸入解釋：相交節點的值為 2 （注意，如果兩個列表相交則不能為 0）。
從各自的表頭開始算起，鏈表 A 為 [0,9,1,2,4]，鏈表 B 為 [3,2,4]。
在 A 中，相交節點前有 3 個節點；在 B 中，相交節點前有 1 個節點。

示例 3:

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

注意：

如果兩個鏈表沒有交點，返回 null.
在返回結果後，兩個鏈表仍須保持原有的結構。
可假定整個鏈表結構中沒有循環。
程式盡量滿足 O(n) 時間複雜度，且僅用 O(1) 記憶體。

二、題解

題解1：哈希表

遍歷鏈表 A 並將每個節點的地址/引用存儲在哈希表中。
然後檢查鏈表 B 中的每一個節點是否在哈希表中。若在，則為相交結點。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
 func getIntersectionNode(headA, headB *ListNode) *ListNode {
    var s [] *ListNode
    
    for headA != nil {
        s = append(s, headA)
        headA = headA.Next
    }
    for headB != nil {
        for _,v := range(s) {
            if v == headB {
                return headB
            }
        }
        headB = headB.Next
    }
    return nil
}

題解2：鏈表拼接法

當鏈表 A 走到尾部的 null 時，轉到鏈表 B 的頭節點繼續走；
當鏈表 B 走到尾部的 null 時，轉到鏈表 A 的頭節點繼續走；
若兩鏈表相交，則 A 和 B 一定相遇。

如上圖：初始化 pA = headA, pB = headB，開始遍歷。
pA會先到達鏈表尾，當pA到達末尾時，重置pA為headB；同樣的，當pB到達末尾時，重置pB為headA。當pA與pB相遇時，必然就是兩個鏈表的交點。

為什麼要這樣處理？因為對 pA 而言，走過的路程為 a+c+b，對 pB 而言，為 b+c+a，顯然 a+c+b = b+c+a，這就是該演算法的核心原理。

即使兩個鏈表沒有相交點，仍然可以統一處理，因為這種情況意味著相交點就是 null，也就是上圖中的公共部分c沒有了，從而遞推式變成了 pA: a+b，pB: b+a，同樣是成立的。

時間複雜度：O(m+n)，空間複雜度：O(1)。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
 func getIntersectionNode(headA, headB *ListNode) *ListNode {
    if (headA == nil || headB == nil) {
        return nil
    }
    pA, pB := headA, headB
    for pA != pB {
        if pA == nil {
            pA = headB 
        } else {
            pA = pA.Next
        }
        if pB == nil {
            pB = headA
        } else {
            pB = pB.Next
        }
    }
    return pA
}

題解3：消除鏈表長度差

兩個單鏈表，有公共結點，則必然尾部公用；

分別找出鏈表 1 和鏈表 2 的長度，長的鏈表減去短的鏈表得出一個 n 值；

長的鏈表先走 n 步，兩個鏈表再同時移動，則兩個鏈表相交點就是第一個公共結點。

時間複雜度：O(n)，空間複雜度：O(1)。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    if headA == nil || headB == nil {
        return nil
    }
    lenA := getLen(headA)
    lenB := getLen(headB)

    //計算鏈表長度差 n，長的先移動 n 步
    if (lenA > lenB) {// 鏈表A比鏈表B長，A先移動
        for i := 0; i < lenA - lenB; i++ {
            headA = headA.Next
        }
    } else {// 鏈表B比鏈表A長，B先移動
        for i := 0; i < lenB - lenA; i++ {
            headB = headB.Next
        }
    }
    
    for headA != nil {
        if headA == headB {
            return headA
        }
        headA = headA.Next
        headB = headB.Next
    }
    return nil;
}

//獲取鏈表長度
func getLen(head *ListNode) int {
    var len int
    for head != nil {
        len++
        head = head.Next
    }
    return len
}

後記

這道題也是面試題中經常遇到的「兩個鏈表的第一個公共節點」。雖然難度是「簡單」，但對我來說一點也不簡單。看評論和題解漲了很多姿勢。

而且，一開始用的是 PHP，可怎麼都通不過，不得不用 Go 重寫了一遍，倒是很快通過了。

附上 PHP 版本：

題解1 PHP版本

class ListNode {
    public $val = 0;
    public $next = null;
    function __construct($val) { 
        $this->val = $val; 
    }
}

/**
 * @param ListNode $headA
 * @param ListNode $headB
 * @return ListNode
 */
function getIntersectionNode($headA, $headB) {
    $hashMap = [];
    while ($headA) {
        $hashMap[] = $headA;
        $headA = $headA->next;
    }
    while ($headB) {
        if (in_array($headB, $hashMap)) {
            return $headB;
        }
        $headB = $headB->next;
    }
    return null;
}

題解2 PHP版本

function getIntersectionNode($headA, $headB) {
    if ($headA == null || $headB == null) {
        return null;
    }

    $pA = $headA;
    $pB = $headB;
    while ($pA != $pB) {
        $pA = $pA == null ? $headB : $pA->next;
        $pB = $pB == null ? $headA : $pB->next;
    }
    return $pA;
}

題解3 PHP版本

function getIntersectionNode($headA, $headB) {
    $lenA = getListLength($headA);
    $lenB = getListLength($headB);

    $diffLen = $lenA > $lenB ? $lenA - $lenB : $lenB - $lenA;
    $headLong = $lenA > $lenB ? $headA : $headB;
    $headShort = $lenA > $lenB ? $headB : $headA;

    //先在長鏈表上走幾步，再同時在兩個鏈表上遍歷
    for ($i = 0; $i < $diffLen; $i++) {
        $headLong = $headLong->next;
    }
    while ($headLong != $headShort) {
        $headLong = $headLong->next;
        $headShort = $headShort->next;
    }
    return $headLong;
}

/**
 * 獲取鏈表的長度
 */
function getListLength($head)
{
    $length = 0;
    $current = $head;
    while ($current != null) {
        $length++;
        $current = $current->next;
    }
    return $length;
}

Tags: LeetCode刷題