[LeetCode] Intersection of Two Linked Lists

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;    }}