Leetcode — 160. Intersection of Two Linked Lists (中文)

問題連結: https://leetcode.com/problems/intersection-of-two-linked-lists/

給予兩個linked list, 找到這兩個list中共同指向的第一個node

如圖, 也就是希望我們找到c1

註:

• 若兩個linked list沒有交集, 則回傳null即可
• 在回傳答案時, 兩個linked lists 需維持他們原本linked list結構
• 可假設任一linked list中都沒有循環
• linked list裡的node的值都會介於[1, 10^9].
• 期望: 時間複雜度為O(n) 且只用O(1) 的空間.

想法:

不知可不可以說這是面試型問題, 畢竟這個問題曾經在Amazon的面試出現過, 不過拿來練習也是不壞
解這題最簡單的方法就是拿一個set 來存所有在linked list A中出現的所有節點, 再一個一個找linked list B裡面的所有節點, 看其節點是否存在於set中.

以下為7ms 程式碼, 贏過26%:

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> set = new HashSet<>();
        while(headA!=null)
        {
            set.add(headA);
            headA = headA.next;
        }
        while(headB!=null)
        {
            if(set.contains(headB))
                return headB;
            headB = headB.next;
        }
        return null;
    }

上述程式碼時間複雜度跟空間複雜度皆為O(n)
在你把這個結果呈現給面試員看後, 很高的機率會被要求問你能不能只用O(1)的空間來完成這題

程式邏輯:

因為我們不知道list A與list B的長度是否相同, 我們需要先做些小技巧 讓他們兩個list有相同長度, 我們才可以進行一對一的比對節點是否相同
為了讓兩者長度相同, 我們可以把比較短的list拉長, 或者把比較長的list縮短; 我們選擇後者, 因為時間複雜度稍微較低, 而且我們也不怕如果把長list縮短會不會有問題, 因為我們將忽略長list的頭幾個"多餘的node", 而這些node我們已知不可能是相交的node (畢竟相交的那個node代表它在兩個list裡面的長度相同)

比如說如下圖, B比A多一個節點 我們就會把原本指著B的指標往後指一個, 這樣一來兩者的指標都指著相同長度的list, 我們就可以來進行比較了

photo credit to Leetcode

因此, 我們可以把我們要做的事情分成三個部分:

1. 找到A跟B的長度, 確定他們是否有相同長度.
2. 若不同長度, 移動指標讓指標可以指著相同長度的list
3. 同時移動兩個指標, 互相比對兩者是否指著同個node

以下為0ms程式碼 贏過100%:

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //step 1
        ListNode temp = headA;
        int lenA=0, lenB=0;
        while(temp!=null)
        {
            temp=temp.next;
            lenA++;
        }
        temp = headB;
        while(temp!=null)
        {
            temp=temp.next;
            lenB++;
        }
        //step 2
        int diff=lenA-lenB;
        while(diff>0) //A is longer
        {
            headA=headA.next;
            diff--;
        }
        while(diff<0) //B is longer
        {
            headB=headB.next;
            diff++;
        }
        //step 3
        while(headA!=null)
        {
            if(headA==headB)
                return headA;
            headA=headA.next;
            headB=headB.next;
        }
        
        return null;
    }

時間複雜度為 O(n), 空間複雜度為 O(1)