LeetCode 160.Intersection of Two Linked Lists (相交連結清單)

題目描述：

編寫一個程式，找到兩個單連結清單相交的起始節點。

例如，下面的兩個連結清單：

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3
      

在節點 c1 開始相交。

注意：

• 如果兩個連結清單沒有交點，傳回 

  null

  .
• 在傳回結果後，兩個連結清單仍須保持原有的結構。
• 可假定整個連結清單結構中沒有循環。
• 程式盡量滿足 O(n) 時間複雜度，且僅用 O(1) 記憶體。

AC C++ Solution:

解題思路：兩連結清單相交的話，後面部分一定是相同的，是以先計算兩連結清單的長度差n；

讓長連結清單先走n步，然後兩連結清單同時周遊，比較每個對應節點。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        
        ListNode *pa = headA, *pb = headB;
        int lengthA = 0, lengthB = 0;
        
        while(pa)   { pa = pa->next; lengthA++; }
        while(pb)   { pb = pb->next; lengthB++; }
        
        
        if(lengthA <= lengthB) {
            pa = headA; pb = headB;
            
            int n = lengthB-lengthA;
            while(n) { pb = pb->next; n--; }
        }
        else {
            pa = headA; pb = headB;
            
            int n = lengthA-lengthB;
            while(n) { pa = pa->next; n--; }
        }
        
        while(pa != pb) {
            pa = pa->next;
            pb = pb->next;
        }
        
        return pa;
    }
};