[LeetCode] Intersection of Two Linked Lists

上次看到這題大概是一年半多前了,會分享這題是因為我今天懶得寫其他題XD

在台北車站附近的NAS大廠面試被問的題目

一開始想到的方法是把list reverse,然後再一起走,但這樣會破壞原有list的結構,或是多用到O(N)的空間

面試官有問 有沒有O(1)的作法

那時候的我真的腦筋動很快阿,現在好像老了沒這個腦了QQ

在白板上畫了兩條線假設了一下長度,就觀察到了

我原先作法是從尾巴走,因為同個位置所以離intersection的位置也會一樣長,所以一起走就可以檢查哪裡是intersection

如果從頭開始走就會受到兩條list長度不一樣的關係,如果可以能從距離一樣的位置開始走就好了!!

所以就是讓長度比較長的pointer先移動這兩條list長度差的距離,讓他們起跑點是一樣的,然後在同時走就好惹

當初我這段是純嘴泡,面試的工程師就點點說對惹,結果沒想到我寫的出來的code好醜

寫完去看了discuss…

別人的方式雖然大同小異卻大大簡化了整個程式

裡面的概念是 兩個pointer A,B同時移動,其中會有一個先抵達tail 假設是 pointer A

那這個pointer A 就從另一條list從頭開始走(這時候兩個pointer的距離就是會兩條線長度的diff)

直到另一個pointer B抵達tail時,這個pointer A2的位置就會是interaction

 

別人的好精簡ORZ QQ