链表与双指针（追及问题）

做链表题目的一个关键是要画图，画出图，标出各段的长度，当成追及问题来做。

剑指offer52.两个链表的第一个公共节点

A-A----
       C-C-C-C-C-C
B-B-B-B

上面的A-C是第一个链表，下面的B-C是第二个链表，设第一个链表在相交节点之前的距离为a，重合节点长度为c，第二个链表在相交节点之前的长度为b。
第一个链表的长度为a+c，第二个链表长度为b+c。
由于要找出某个节点，最后一定会让两个指针相交于某点。
所以两个指针从两个链表头节点开始移动，速度一样，链表一上的节点到了尾节点时，走了a+c，此时把它重新指向链表二的头节点
链表二的节点走到了尾节点，走了b+c，此时把它重新指向链表一的头节点
容易发现，二者将会相交于第一个公共节点，两个节点都走了a+b+c的长度。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p1=headA;
        ListNode p2=headB;

        while(p1!=p2){
            if(p1!=null){p1=p1.next;}else{p1=headB;}
            if(p2!=null){p2=p2.next;}else{p2=headA;}
        }
        return p1;       
    }
}

leet142.环形链表2
设置fast指针，一次走两格，设置slow指针，一次走一格。
因为有环，速度又不同，所以两个指针一定会相遇，设相遇时慢指针走了s，那么快指针走了2s。
因为二者相遇，说明当快指针走到s之后，又走了n倍的环长，设环长为b，那么2s=s+nb。
s=nb，也就是说在第一次相遇时，二者都走了n倍的环长。
此时把快指针重新指向头节点，并把速度降到与慢指针一样。这样，当快指针再走到环的开头时，设距离为a，那么从整个时间来说，慢指针走了a+nb。也就是会相交。
反过来说，再相交时就是环的入口。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        //获取首次相遇时候，slow的位置
        while(fast!= null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                break;
            }
        }
        //如果快指针走到尽头，没环
        if(fast == null || fast.next == null) return null;
        //快指针重新出发，相遇位置就是入口位置
        fast = head;
        while(fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

这样的问题，相遇是最关键的，要分析相遇时走的步长。
另外，相遇后都至少得对其中一个指针进行变化，无论是变速度还是变位置，在这个变动之后，对已变动的指针要看变动后的距离，
对未变动的指针要看全时间的距离，这样，就能分析出来。