LeetCode 142:环形链表入口

题目：

题解：

代码示例：

package com.zy.leetcode.LeetCode_142;

/**
 * @Author: zy
 * @Date: 2025-01-03-15:13
 * @Description: 找出链表的环形入口
 */
public class ListNode_142 {

    private int val;

    private ListNode_142 next;
    ;

    public ListNode_142(int x) {
        val = x;
    }

    public ListNode_142(int x, ListNode_142 next) {
        val = x;
        this.next = next;
    }

    //链表打印
    public static void printList(ListNode_142 head) {
        ListNode_142 p = head;
        while (p != null) {
            System.out.print(p.val + " -> ");
            p = p.next;
        }
        System.out.println("null");
    }

    /**
     * 找到链表的环形链表入口节点
     *
     * @param head
     * @return
     */
    public ListNode_142 detectCycle(ListNode_142 head) {
        ListNode_142 slow = head;
        ListNode_142 fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            /**
             * 相遇之后，快和慢都：步 都为1
             */
            if (slow == fast) {
                // 相遇，有环
                ListNode_142 meetNode = slow;
                ListNode_142 p = head;
                while (p != meetNode) {
                    p = p.next;
                    meetNode = meetNode.next;
                }
                return p;
            }
        }
        return null;

    }

    /**
     * 当环首尾相接，极有可能出问题
     *
     * @param head
     * @return
     */
    public ListNode_142 detectCycle2(ListNode_142 head) {
        ListNode_142 t = head;
        ListNode_142 h = head;

        // 第一阶段
        while (h != null && h.next != null) {
            t = t.next;
            h = h.next.next;
            /**
             * 相遇之后，快和慢都：步 都为1
             */
            if (t == h) {
                // 相遇，有环
                t = head;
                while (true) {
                    t = t.next;
                    h = h.next;
                    if (t == h) {
                        return t;
                    }
                }
            }
        }
        return null;

    }

    public static void main(String[] args) {
        ListNode_142 head = new ListNode_142(1);
        ListNode_142 node2 = new ListNode_142(2);
        ListNode_142 node3 = new ListNode_142(3);
        ListNode_142 node4 = new ListNode_142(4);
        ListNode_142 node5 = new ListNode_142(5);

        head.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node2; // 形成环

        ListNode_142 result = head.detectCycle(head);
        if (result != null) {
            System.out.println("环形入口节点为： " + result.val);
        } else {
            System.out.println("无环");
        }

        ListNode_142 result1 = head.detectCycle2(head);

        if (result1 != null) {
            System.out.println("环形入口节点为： " + result1.val);
        } else {
            System.out.println("无环");
        }

    }

}