1. Intersection of Two Linked Lists
2. Linked List Cycle II

1. Intersection of Two Linked Lists

1. find length + 较长的list先move 多出来的几步 + 一起走
2. when reach end, switch to the head of the other list

• 如果intersect的话，要不然两个list长度一样，要不然不一样。如果不一样的话，较长的List先走几步，直到两个head离tail的步数是一样的。这个时候两个heads一起移动，如果有intersect，那么就一定会在交汇点相遇。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    int Alen = getLength(headA);
    int Blen = getLength(headB);
    int diff = Math.abs(Alen - Blen);
    if (Alen > Blen) {
        while (diff > 0) {
            headA = headA.next;
            diff--;
        }
    } else if (Alen < Blen) {
        while(diff > 0) {
            headB = headB.next;
            diff--;
        }
    }
    while(headA != null && headB != null) {
        if (headA == headB) return headA;
        headA = headA.next;
        headB = headB.next;
    }
    return null;
}

private int getLength(ListNode node) {
    int i = 0;
    while (node != null) {
        node = node.next;
        i++;
    }
    return i;
}

• 当一条list到尾巴的时候，换到另一条的开头去。

  • 到尾巴的时候，A & B链都要记录下尾巴。因为如果没有Intersect的话，两个尾巴就是不一样的。以此来判断两条链是不是相交了

  To see why the above trick would work, consider the following two lists: A = {1,3,5,7,9,11} and B = {2,4,9,11}, which are intersected at node '9'. Since B.length (=4) < A.length (=6), pB would reach the end of the merged list first, because pB traverses exactly 2 nodes less than pA does. By redirecting pB to head A, and pA to head B, we now ask pB to travel exactly 2 more nodes than pA would. So in the second iteration, they are guaranteed to reach the intersection node at the same time.

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    ListNode tailA = null, tailB = null;
    ListNode currA = headA, currB = headB;
    while(true) {
        if (currB == null) {
            currB = headA;
        }
        if (currA == null) {
            currA = headB;
        }
        if (currA.next == null) {
            tailA = currA;
        }
        if (currB.next == null) {
            tailB = currB;
        }
        if (tailA != null && tailB != null && tailA != tailB) return null;//no circle
        if (currA == currB) return currA;
        currA = currA.next;
        currB = currB.next;
    }
}

2. Linked List Cycle II

fast, slow pointer both starts from the head node.

先检测有没有cycle。通过快慢指针同时从head出发，来判断。如果fast 指针追上了slow指针的话，那么就说明有cycle。

这时候，再用两个指针，一个从head node出发，一个从相逢的地方出发，那么他们相遇的地方就是入口了。

原理看下图。