链表双指针：到底该走几步？

环形链表II和相交链表

环形链表

判断一个链表是否有环，最基本的双指针方法。

public class Solution {
    public boolean hasCycle(ListNode head) {
        //快慢指针 slow每次走1格 fast每次走2格
        if(head==null) return false;
        ListNode slow = head;
        if(slow.next==null) return false;
        ListNode fast = slow.next.next;
       
        while (fast != null) {
            if (slow == fast) return true;  //当快慢指针相遇 说明存在环
            else {
                slow = slow.next;
                if(fast.next==null) return false;
                fast = fast.next.next;
            }
        }
        //没有环的最终会推出循环
        return false;
    }
}

但是，如果想要判断环形链表中环的起点时，就要考虑快慢指针走了多少次。

假设从链表起点出发到环起点的距离为a，环的长度为b，现有快慢指针fast和slow第一次相遇。

fast 走的步数是slow步数的 2倍，即f = 2s；
fast比 slow多走了 n 个环的长度，即f = s + nb；（解析: 双指针都走过a步，然后在环内绕圈直到重合，重合时 fast 比 slow 多走环的长度整数倍）
以上两式相减得：f = 2nb, s = nb

现在考虑环的起点位置为：a+nb，所以， slow指针 位置不变 ，将fast指针重新 指向链表头部节点 ；slow和fast同时每轮向前走 a 步，两个结点再次重合，该节点即为环的起点。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode slow = head, fast = head;
        while (true) {
            slow = slow.next;
            if (fast==null||fast.next == null) {
                return null;
            } else {
                fast = fast.next.next;
            }
            if (slow == fast) break;
        }
        fast = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

相交链表

找到两个单链表相交的起始节点，记链表长度分别为a和b，可以考虑fast结点先走 abs(a-b) 步，然后fast和slow指针在同时往后走直到相交结点。但是获得lenA和lenB需要多次遍历链表。

现在考虑如何减少遍历的次数。

设链表A的长度为a，链表B的长度为b，A到相交结点的距离为c,B到相交节点的距离为d。

显然可以得到两者相交链表的长度：a - c = b - d，

变换一下式子得到：a + d = b + c。

用一个指针从链表A出发，到末尾后就从B出发，用另一个指针从B出发，到末尾后从A出发，

当前一个指针走了a+d步数时，后一个指针走了b+c,两步数相等，即走到了相交节点。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode q = headA, p = headB;
        while (q != p) {
            if (q != null) {
                q = q.next;
            } else {
                q = headB;
            }
            if (p != null) {
                p = p.next;
            } else {
                p = headA;
            }
        }
        return q;
    }
}

1	public class Solution {
2	public boolean hasCycle(ListNode head) {
3	//快慢指针 slow每次走1格 fast每次走2格
4	if(head==null) return false;
5	ListNode slow = head;
6	if(slow.next==null) return false;
7	ListNode fast = slow.next.next;
8
9	while (fast != null) {
10	if (slow == fast) return true; //当快慢指针相遇说明存在环
11	else {
12	slow = slow.next;
13	if(fast.next==null) return false;
14	fast = fast.next.next;
15	}
16	}
17	//没有环的最终会推出循环
18	return false;
19	}
20	}

1	public class Solution {
2	public ListNode detectCycle(ListNode head) {
3	if (head == null \|\| head.next == null) {
4	return null;
5	}
6	ListNode slow = head, fast = head;
7	while (true) {
8	slow = slow.next;
9	if (fast==null\|\|fast.next == null) {
10	return null;
11	} else {
12	fast = fast.next.next;
13	}
14	if (slow == fast) break;
15	}
16	fast = head;
17	while (slow != fast) {
18	slow = slow.next;
19	fast = fast.next;
20	}
21	return slow;
22	}
23	}

1	public class Solution {
2	public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
3	ListNode q = headA, p = headB;
4	while (q != p) {
5	if (q != null) {
6	q = q.next;
7	} else {
8	q = headB;
9	}
10	if (p != null) {
11	p = p.next;
12	} else {
13	p = headA;
14	}
15	}
16	return q;
17	}
18	}