[LeetCode] Intersection of Two Linked Lists

上次看到這題大概是一年半多前了，會分享這題是因為我今天懶得寫其他題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