【Java算法题解】剑指 Offer II 022. 链表中环的入口节点

JavaEdge

发布于 2021-10-18 16:25:03

2760

文章被收录于专栏：JavaEdgeJavaEdge

解析

先通过快慢指针判断有无环

无环

直接返回null

有环

假设起点到环起点的距离是a，环的长度是k，且此时A、B在距离环起点x距离处相遇。

即慢指针再走x步就到达环的入口，此时slow走过的距离

a + nk + (k - x)

快指针走过的距离：

a + mk + (k - x)

由快慢的定义可知：

a + mk + (k - x) = 2 * (a + nk + (k - x))

化简得：

 a = (m - 2n -1)k + x

可知a为k的整数倍加x，而AB相遇的位置再走x步恰是环入口，所以此时让其中一个指针指向起点，然后同步走，一定能在环入口相遇！

所以可得代码：

package com.javaedge;

/**
 * @author JavaEdge
 * @date 2021/8/17
 */
public class DetectCycle {

    static class ListNode {
        int val;
        ListNode next;

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

    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        boolean isCircled = false;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                isCircled = true;
                break;
            }
        }
        if (!isCircled) {
            // 无环
            return null;
        }

        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021/08/18 ，如有侵权请联系 cloudcommunity@tencent.com 删除

null