160. Intersection of Two Linked Lists

發表於 更新於 分類於 ， 閱讀次數： 文章字數： 2.4k

種類 : linked list
難度 : eazy
題目 : 160. Intersection of Two Linked Lists

思維邏輯

  1. 歷遍A的同時與B比較(❌錯誤)
    graph LR
A[4] --> B[1] --> C[8] --> D[4] --> E[5]
F[5] --> G[6] --> H[1] --> C

解法

第1次(❌錯誤: 未考慮location in memory & 超時)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
"""
A: 4 -> 1 ->
                  8 -> 4 -> 5
B: 5 -> 6 -> 1->
Intersected at '8''
範例已特別說明輸出為 "8->4->5"，而非 "1->8->4->5"
"""
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        # 歷遍A的同時，與B每個元素比較，若相同時存入intersect並break
        curA, curB = headA, headB
        intersect = None

        while curA.next:
            curB = headB
            while curB.next:
                if curA != curB:
                    curB = curB.next
                else:
                    intersect = curB
                    break
            curA = curA.next
        return intersect

第2次(❌錯誤: 超時)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
"""
使用虛擬head比較curA.next與curB.next
"""
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        dummyA = ListNode(next=headA)
        dummyB = ListNode(next=headB)
        curA, curB = dummyA, dummyB
        intersect = None

        while curA.next:
            curB = dummyB
            while curB.next:
                if curA.next != curB.next:
                    curB = curB.next
                else:
                    intersect = curB.next
                    break
            if intersect:
                break
            curA = curA.next
        return intersect

listA.size = n, listB.size = m
時間複雜度: O(n*m)
空間複雜度: O(1)

難點

  1. 使用兩層迴圈雖然可通過測試，但效率仍不及單層(對齊list)好
  2. 對齊list時，雖需歷遍兩個lists，但時間複雜度相對比較低

最佳解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
"""
對齊兩個lists
"""
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        dummyA = ListNode(next=headA)
        dummyB = ListNode(next=headB)

        # 計算長度
        sizeA, sizeB = 0, 0
        curA, curB = dummyA, dummyB
        while curA.next:
            sizeA += 1
            curA = curA.next
        while curB.next:
            sizeB += 1
            curB = curB.next

        # 對齊A, B
        curA, curB = dummyA, dummyB
        if sizeA > sizeB:
            for _ in range(sizeA-sizeB):
                curA = curA.next
        else:
            for _ in range(sizeB-sizeA):
                curB = curB.next
        
        while curA.next:
            if curA.next != curB.next:
                curA = curA.next
                curB = curB.next
            else:
                return curA.next

listA.size = n, listB.size = m
時間複雜度: O(n+m)
空間複雜度: O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
"""
等比例法(雙指針切換路徑法)
"""
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        # 处理边缘情况
        if not headA or not headB:
            return None
        
        # 在每个链表的头部初始化两个指针
        pointerA = headA
        pointerB = headB
        
        # 遍历两个链表直到指针相交
        while pointerA != pointerB:
            # 将指针向前移动一个节点
            # 💡 這裡else不是指向另一個pointer，而是另一個head
            pointerA = pointerA.next if pointerA else headB
            pointerB = pointerB.next if pointerB else headA
        
        # 如果相交，指针将位于交点节点，如果没有交点，值为None
        return pointerA

時間複雜度: O(n+m)
空間複雜度: O(n)