Write a PRogram to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

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

begin to intersect at node c1.

Notes:

• If the two linked lists have no intersection at all, returnnull.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

這道題還是先要搞懂題目問的啥。這里的intersection linked list通過看例子我們可以看出，其length可以不一樣，但是從intersect的部分開始到結束長度是一樣的，所以說多余的只會是前面的幾個值，而且一定有較長length的那個linked list多余出來的那一段的值。

所以我們首先計算兩個list的length，把較長的那個的多余的那部分的值給waive掉。這樣兩條同樣長的list就非常好找intersect的地方了。

代碼如下。~

/** * 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) {        int lengtha=0;        int lengthb=0;        ListNode curr1=headA;        ListNode curr2=headB;        while(curr1!=null){            lengtha++;            curr1=curr1.next;        }        while(curr2!=null){            lengthb++;            curr2=curr2.next;        }        curr1=headA;        curr2=headB;        if(lengtha>lengthb){            for(int i=0;i<lengtha-lengthb;i++){                curr1=curr1.next;            }        }else{            for(int i=0;i<lengthb-lengtha;i++){            curr2=curr2.next;            }        }        while(curr1!=curr2){            curr1=curr1.next;            curr2=curr2.next;        }        return curr1;    }}