LeetCode 160. Intersection of Two Linked Lists [Easy] [C++] 解題筆記

 Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

For example, the following two linked lists begin to intersect at node c1:

It is guaranteed that there are no cycles anywhere in the entire linked structure.

Note that the linked lists must retain their original structure after the function returns.

 

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'
Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

Example 2:

Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Intersected at '2'
Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [1,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3:

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: No intersection
Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.

 

Constraints:

• The number of nodes of listA is in the m.
• The number of nodes of listB is in the n.
• 0 <= m, n <= 3 * 104
• 1 <= Node.val <= 105
• 0 <= skipA <= m
• 0 <= skipB <= n
• intersectVal is 0 if listA and listB do not intersect.
• intersectVal == listA[skipA + 1] == listB[skipB + 1] if listA and listB intersect.

 

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

想法:

          這題簡單的作法是先判斷兩個 list 的長度，因為若兩個 list 的長度相等那我們就只需要逐個比較即可，如果其中一邊比較長那摸就將較長的那個 list 先向後移動兩者的長度差，這樣就把問題簡化成相等長度逐個比較了。(因為在 interact 的 node 之後兩個 list 是長一樣的，所以長度不一樣的話一定是在 interact 的 node 之前不一樣)

          另外這題有另一個比較有技巧性也很簡潔的方法，假設 list A 的長度為 len(A)，list B 的長度為 len(B)，我們讓兩個指標分別從 A 與 B 的開頭走且若走到底則換到另一個list的開頭繼續走，直到兩者相等，如果 A 與 B 有交集則相等的位置會是交集的點，若 A 與 B 沒有交集則相等的點會是兩者的結尾(nullptr)，因為兩個指標最多都會走 len(A) + len(B) 個點，因此若 A 與 B 沒有交集時兩個指標皆會停在結尾(nullptr)處。

完整程式碼:

class Solution {

public:

    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {

        auto cur_a = headA;

        auto cur_b = headB;

        while (cur_a != cur_b) {

            cur_a = (cur_a == NULL)? headB : cur_a->next;

            cur_b = (cur_b == NULL)? headA : cur_b->next;

        }

        

        return cur_a;

    }

};