160 Intersection of Two Linked Lists

Concept: 先找出A和B的長度 a, b 讓長的那個先走|a-b|步 再讓A和B同時前進，直到走到intersect node。

如果不這樣做，即使兩個linked list有intersection node，你也不知道該分別走幾步，才能比較兩邊的ListNode。所以要從tail端往前算，讓兩邊都從tail端往前一樣的長度的地方開始往後trace。

Java程式碼如下:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        ListNode ptA = headA;
        ListNode ptB = headB;
        int lenA=0, lenB=0;
        while(ptA!=null){
            lenA++;
            ptA = ptA.next;
        }
        while(ptB!=null){
            lenB++;
            ptB = ptB.next;
        }
        ptA = headA;
        ptB = headB;
        if(lenA > lenB){
            for(int i=0; i<lenA-lenB; i++){
                ptA = ptA.next;
            }
        }
        if(lenB > lenA){
            for(int i=0; i<lenB-lenA; i++){
                ptB = ptB.next;
            }
        }
        while(ptA!=null){
            if(ptA == ptB)  return ptA;
            ptA = ptA.next;
            ptB = ptB.next;
        }
        return null;
    }
}