剑指Offer Java版 面试题23：链表中环的入口节点

题目：给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

练习地址

https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4

参考答案

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if (pHead == null || pHead.next == null) {
            return null;
        }
        ListNode meetingNode = meetingNode(pHead);
        if (meetingNode == null) {
            return null;
        }
        // 得到环中节点的数目
        ListNode cur = meetingNode.next;
        int nodesInLoop = 1;
        while (cur != meetingNode) {
            nodesInLoop++;
            cur = cur.next;
        }
        ListNode behind = cur = pHead;
        // 先移动cur，次数为环中节点的数目
        while (nodesInLoop-- > 0) {
            cur = cur.next;
        }
        // 再移动behind和cur，相遇时即为入口节点
        while (behind != cur) {
            behind = behind.next;
            cur = cur.next;
        }
        return behind;
    }
    
    private ListNode meetingNode(ListNode pHead) {
        // 在链表中存在环时找到一快一慢两个指针相遇的节点，无环返回null
        ListNode cur = pHead.next.next, behind = pHead;
        while (cur != null) {
            if (cur == behind) {
                return cur;
            }
            if (cur.next != null) {
                cur = cur.next.next;
            } else {
                return null;
            }
            behind = behind.next;
        }
        return null;
    }
}

复杂度分析

• 时间复杂度：O(n)。
• 空间复杂度：O(1)。

👉剑指Offer Java版目录
👉剑指Offer Java版专题