CodingInterviews icon indicating copy to clipboard operation
CodingInterviews copied to clipboard

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

Open H-ZeX opened this issue 6 years ago • 0 comments

来自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长度
      • ba多走的可以分成两段
        • 第一部分是从相遇点到环的终点
        • 第二部分是从环的起点到相遇点
      • 第二部分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;
        }
    }

H-ZeX avatar Feb 18 '19 05:02 H-ZeX