相交链表

编写一个程序，找到两个单链表相交的起始节点。

注意:

如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

思路

两条链表长度相减，得到长度之差count，再让长的链表走count步，然后两条链表同时走，即可得到相交的节点

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a=headA;
        ListNode b=headB;
        int lenA=0,lenB=0;
        while(a!=null){
            a=a.next;
            lenA++;
        }
        
        while(b!=null){
            b=b.next;
            lenB++;
        }
        
        int count=0;
        if(lenA>=lenB){
            count=lenA-lenB;
            for(int i=0;i<count;++i){
                headA=headA.next;
            }
        }else{
            count=lenB-lenA;
            for(int i=0;i<count;++i){
                headB=headB.next;
            }
        }
        
        while(headA!=headB){
            headA=headA.next;
            headB=headB.next;
        }
        
        return headA;
    }
}