Leetcode No.160(Intersection of Two Linked Lists) 心得

ChingYuanYang
Aug 25, 2017 · 2 min read

題目:

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2

c1 → c2 → c3

B: b1 → b2 → b3

begin to intersect at node c1.

Notes:

  • If the two linked lists have no intersection at all, return null.
  • The linked lists must retain their original structure after the function returns.
  • You may assume there are no cycles anywhere in the entire linked structure.
  • Your code should preferably run in O(n) time and use only O(1) memory.

想法:
這題的關鍵在於若是兩個list有相交,最後一個node會相同。如果是 double linked list 很簡單,往回推就可以了。這題是 single linked list,並且只能用O(1) memory,那我想的方法就是先去找出每個 list 長度,相減之後就是長的 list 多出一定不會相交的部分。這時候長的 list 就先跳過這個部分,此時再兩兩互相比較。

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int countA = 1;
int countB = 1;
ListNode* tmpA = headA;
ListNode* tmpB = headB;
if (tmpA == NULL || tmpB == NULL)
return NULL;
while(tmpA->next != NULL){
countA++;
tmpA = tmpA->next;
}
while(tmpB->next != NULL){
countB++;
tmpB = tmpB->next;
}
tmpA = headA;
tmpB = headB;
int diff = abs(countA — countB);
if (countA > countB) {
for (int i = 0; i < diff; i++)
tmpA = tmpA->next;
} else {
for (int i = 0; i < diff; i++)
tmpB = tmpB->next;
}

while (tmpA != NULL) {
if (tmpA == tmpB)
return tmpA;
tmpA = tmpA->next;
tmpB = tmpB->next;
}
return NULL;
}
};

網路上解答:
其實概念和我的想法差不多,只是用另一個方法描述: A list 走到底後接著走 B list,B list 也做同一件事情。這個方法聰明在於不用記錄 list 長度,短的 list 會被先走完就會換到長的 list 去,所以此時長的 list 就會被先走。

示意圖:
共同的node: Common
listA = A + Common
listB =B + Common
PointerA: [A + Common + B] + Common
PointerB: [B + Common + A] + Common

所以當兩邊第一個的 common 走完(走到最後一個node),就可以兩兩互相比較,一定一起走到下一個 Common,因為 [A + Common + B] = [B + Common + A]。

網路上找到很簡單幾行程式,但是他的缺點是他從開頭就兩兩互相比較,我認為若要加速應該要從兩個 pointer 都走到最後一個 node 要從另一個 list 頭開始走的時候再兩兩互相比較。

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *cur1 = headA, *cur2 = headB;
while(cur1 != cur2){
cur1 = cur1?cur1->next:headB;
cur2 = cur2?cur2->next:headA;
}
return cur1;
}

另外一個方法是用 hash table,儲存一條 list node 的 address,另外一條再一個個比對,缺點是 Space complexity : O(m) or O(n)。Time complexity一樣。
Time complexity : O(m+n)。

)
Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade