上次看到這題大概是一年半多前了,會分享這題是因為我今天懶得寫其他題XD
在台北車站附近的NAS大廠面試被問的題目
一開始想到的方法是把list reverse,然後再一起走,但這樣會破壞原有list的結構,或是多用到O(N)的空間
面試官有問 有沒有O(1)的作法
那時候的我真的腦筋動很快阿,現在好像老了沒這個腦了QQ
在白板上畫了兩條線假設了一下長度,就觀察到了
我原先作法是從尾巴走,因為同個位置所以離intersection的位置也會一樣長,所以一起走就可以檢查哪裡是intersection
如果從頭開始走就會受到兩條list長度不一樣的關係,如果可以能從距離一樣的位置開始走就好了!!
所以就是讓長度比較長的pointer先移動這兩條list長度差的距離,讓他們起跑點是一樣的,然後在同時走就好惹
當初我這段是純嘴泡,面試的工程師就點點說對惹,結果沒想到我寫的出來的code好醜
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