Leetcode No.160(Intersection of Two Linked Lists) 心得
題目:
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 → b3begin 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)。
