链表中环的入口结点的双指针简单解法

[H-ZeX]

来自leetcode讨论区

基本思路

• 两个指针，a每次走一步，b每次走两步
• 相遇后，a设为list的开头，b不变，然后a、b同时走直到相遇

证明

• 设
  • 第一次，经过k步相遇
  • 链的起点到环的起点为s长度
  • 环的起点到第一次相遇的点距离为m
  • 环的长度为r
• 所以
  • 2k-k=nr=r
  • s=k-m=r-m
    • 因为a走了不到整条链，比整条链少r-m长度，然后b走了整条链加上m长度
    • b比a多走的可以分成两段
      • 第一部分是从相遇点到环的终点
      • 第二部分是从环的起点到相遇点
    • 第二部分a也走过（所以这一部分b刚好走过两倍a走过的长度）
    • 所以，第一部分就是等价于a从链的起点到环的起点
  • 从而，只要一起再走r-m步就可以相遇

代码

    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public class Solution {
        public ListNode detectCycle(ListNode head) {
            ListNode p1 = head, p2 = head;
            while (p1 != null && p2 != null) {
                p1 = p1.next;
                if (p2.next == null) {
                    return null;
                }
                p2 = p2.next.next;
                if (p1 == p2) {
                    break;
                }
            }
            if (p1 == null || p2 == null) {
                return null;
            }
            p1 = head;
            while (p1 != p2) {
                p1 = p1.next;
                p2 = p2.next;
            }
            return p1;
        }
    }