上次看到這題大概是一年半多前了，會分享這題是因為我今天懶得寫其他題XD
在台北車站附近的NAS大廠面試被問的題目
一開始想到的方法是把list reverse，然後再一起走，但這樣會破壞原有list的結構，或是多用到O(N)的空間
面試官有問 有沒有O(1)的作法
那時候的我真的腦筋動很快阿，現在好像老了沒這個腦了QQ
在白板上畫了兩條線假設了一下長度，就觀察到了
我原先作法是從尾巴走，因為同個位置所以離intersection的位置也會一樣長，所以一起走就可以檢查哪裡是intersection
如果從頭開始走就會受到兩條list長度不一樣的關係，如果可以能從距離一樣的位置開始走就好了！！
所以就是讓長度比較長的pointer先移動這兩條list長度差的距離，讓他們起跑點是一樣的，然後在同時走就好惹
當初我這段是純嘴泡，面試的工程師就點點說對惹，結果沒想到我寫的出來的code好醜
|
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 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { if(headA == NULL || headB == NULL) return NULL; ListNode *tail_A = NULL, *tail_B = NULL; ListNode *tmpA = headA, *tmpB = headB; int lenA = 1, lenB = 1, count = 0, diff; while(tmpA->next != NULL) { tmpA = tmpA->next; lenA++; } while(tmpB->next != NULL) { tmpB = tmpB->next; lenB++; } tail_A = tmpA; tail_B = tmpB; if(tail_A != tail_B) return NULL; while(count != abs(lenA -lenB)) { if(lenA > lenB) headA = headA->next; else if(lenA < lenB) headB = headB->next; count++; } while(headA != headB) { headA = headA->next; headB = headB->next; } return headA; } }; |
寫完去看了discuss…
別人的方式雖然大同小異卻大大簡化了整個程式
裡面的概念是 兩個pointer A,B同時移動，其中會有一個先抵達tail 假設是 pointer A
那這個pointer A 就從另一條list從頭開始走（這時候兩個pointer的距離就是會兩條線長度的diff)
直到另一個pointer B抵達tail時，這個pointer A2的位置就會是interaction
別人的好精簡ORZ QQ
