160 相交链表

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

方法一：
分三个步骤：

1. 获得两个链表的长度，相减得到长度差。
2. 让长的链表先走长度差步
3. 两个链表一起走，直到碰上相同的节点返回

注意：
边界处理

代码：

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    int lenA = getLength(headA);
    int lenB = getLength(headB);
    int diff = Math.abs(lenA - lenB);
    if(lenA > lenB){
        for(int i = 0; i < diff; i++)
            headA = headA.next;
    }
    if(lenB > lenA){
        for(int i = 0; i < diff; i++)
            headB = headB.next;
    }
    while(headA != headB){
        headA = headA.next;
        headB = headB.next;
    }
    return headA;
}

public int getLength(ListNode head){
    if(head == null)
        return 0;
    int count = 0;
    ListNode cur = head;
    while(cur != null){
        count++;
        cur = cur.next;
    }
    return count;
}

方法二：
设链表A前半部分长度为a，链表B前半部分长度为b，链表A和链表B相交的部分长度为c。
易知：a + c + b = a + b + c

因此我们先让指针curA在链表A上走a+c步，走到链表A末尾后，再让curA从链表B的头部开始走，在链表B上再走b步。

同理：让指针curB在链表B上走b+c步，走到链表B末尾后，再让curB从链表A的头部开始走，在链表A上再走a步。

这样当两个指针都走了a+b+c步时，它们会相遇于两个链表的交点。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode curA = headA;
    ListNode curB = headB;
    while(curA != curB){
        curA = (curA == null) ? headB : curA.next;
        curB = (curB == null) ? headA : curB.next;
    }
    return curA;
}