繼第一天的「Day 1 - 1. Two Sum - 解法與複雜度 - LeetCode in Swift」，今天來解 160 這題！還沒看過第一天的朋友，歡迎也去看看~

我們開始吧！

基本資訊

難度： Easy / Medium
網址： https://leetcode.com/problems/intersection-of-two-linked-lists/

題意

給予兩個單項鏈結串列 (Singly Linked List) 的 head 節點 headA 和 headB ，回傳兩個 link lists 開始交集的節點；如果沒有交集則回傳 null 。

範例

listA = [4,1,8,4,5]
listB = [5,6,1,8,4,5]

開始交集的地方就是這個節點：

8

直觀解法 - Hash Table

class Solution {
    func getIntersectionNode(_ headA: ListNode?, _ headB: ListNode?) -> ListNode? {
        var aSet = Set<ListNode>()

        var a = headA
        while let unwrappedA = a {
            aSet.insert(unwrappedA)
            a = unwrappedA.next
        }

        var b = headB
        while let unwrappedB = b {
            if aSet.contains(unwrappedB) { return unwrappedB }
            b = unwrappedB.next
        }

        return nil
    }
}

// 為了能存入 Set 必須幫 ListNode 加上 Hashable 實作
extension ListNode: Hashable {
    public func hash(into hasher: inout Hasher) {
        hasher.combine(ObjectIdentifier(self))
    }

    public static func == (lhs: ListNode, rhs: ListNode) -> Bool {
        return ObjectIdentifier(lhs) == ObjectIdentifier(rhs)
    }
}

執行結果

• Runtime: 226 ms (Beats 55.63%)
• Memory: 17.07 MB (Beats 16.20%)

複雜度

令 listA 的個數為 m, listB 的個數為 n

• 時間複雜度： O(m+n)
  • 最壞情形之下，兩者都需要完整走過
• 空間複雜度： O(m)
  • 需要把 listA 存入一個同樣大小的 Set 物件，因此為 O(m)

解說

分兩個主要的步驟，和一個結束條件

1. 將第一個 linked list 的所有節點加入一個 Set
2. 走訪第二個 linked list ，逐一節點檢查是否有在該 Set 中，有則回傳該節點，結束運算
3. 當走訪完又沒有找到時，則回傳 nil

提早結束

在許多情境下，我們可以試著提早結束運算來節省時間和資源。

以這個寫法為例，可以加一行判斷如下：

class Solution {
    func getIntersectionNode(_ headA: ListNode?, _ headB: ListNode?) -> ListNode? {
        // !!!: 如果其中一個節點為 nil ，就可以提早結束：
        if headA == nil || headB == nil { return nil }

        var aSet = Set<ListNode>()

        var a = headA
        while let unwrappedA = a {
            aSet.insert(unwrappedA)
            a = unwrappedA.next
        }

        var b = headB
        while let unwrappedB = b {
            if aSet.contains(unwrappedB) { return unwrappedB }
            b = unwrappedB.next
        }

        return nil
    }
}

/* Hashable 實作省略 */

進階解法 - 合併走訪 linked lists

想法和觀察

以這兩個字串為例

  4,1,8,4,5
5,6,1,8,4,5

可以發現全部置右對齊之後，交集的地方很容易就可以找到了。

但是因為資料結構是 singly linked list ，所以無法從尾端走訪；而我們可以發現當先走訪對方那組的之後，就可以把需要比較的對象像上面那樣置右了。

排排站之後像是這樣：

5,6,1,8,4,5|4,1,8,4,5
4,1,8,4,5|5,6,1,8,4,5

根據這個觀察，可以得出核心 routine 的邏輯會是

1. 判斷 a 是否和 b 相等
2. a 先走訪完 listA 再走訪 listB
3. b 先走訪完 listB 再走訪 listA

結束條件是 a === b ，而這個相等有兩個含意

1. 兩者相等，且不是 nil ，代表有交集
2. 兩者相等，且都是 nil ，代表無交集

無論是任意一種結束走訪，我們都可以說 a 和 b 都是我們要的結果，因此可以直接回傳 a 或是 b。

程式碼

class Solution {
    func getIntersectionNode(_ headA: ListNode?, _ headB: ListNode?) -> ListNode? {
        if headA == nil || headB == nil { return nil }

        var a = headA
        var b = headB
        
        // 因為是要比較記憶體位置，所以使用 !==
        // 當兩者沒有相同時，則繼續走訪
        while a !== b {
            // 核心 routine
            a = a == nil ? headB : a?.next
            b = b == nil ? headA : b?.next
        }

        // or return b
        return a
    }
}

執行結果

• Runtime: 225 ms (Beats 57.75%)
• Memory: 16.55 MB (Beats 84.51%)

複雜度

令 listA 的個數為 m, listB 的個數為 n

• 時間複雜度： O(m+n)
  • 最壞情形之下，兩者都需要完整走過 -> 2m + 2n -> m + n
• 空間複雜度： O(1)
  • 不需要另外的空間來暫存節點

解法比較

第二個合併走訪的解法為符合題目中應對 Follow Up 的解法，官方解答在這個解法還有特別註記這個解法屬於 Medium 。而第一個解法實際上也比較接近在面試時會看到的解法和水準。

Follow up: Could you write a solution that runs in O(m + n) time and use only O(1) memory?

從執行數據來看兩種解法的執行時間差不多，而第二個解法所使用的記憶體較少，但是似乎少到可以忽略可以說是差不了多少。

結語

當初知道這題的第二個解法時，無法整理出能讓自己認同的一個夠有說服力的解法，但是還是想要嘗試寫出來看看。所以當中有任何文中寫不清楚的地方和回饋，都歡迎在下面留言！

今天的解題文章就到這裡，明天見！