当前位置：首页 > news >正文

链表中环的入口节点 -- java

news 来源：原创 2024/5/14 9:48:12

题目描述

如果一个链表中包含环，如何找出环的入口节点？例如，在如下图所示的链表中，环的入口节点是节点3。

在这里插入图片描述

解题思路

确定一个链表中包含环
用两个指针指向头节点指针，同时从链表的头节点触发，一个指针一次走一步，另一个指针一次走两步。如果走得快的指针追上了走得慢的指针，那么链表就包含环，如果的走得快的指针走到了链表的末尾都没有追上走得慢的指针，那么链表就不包含环。
找到环的入口
用两个指向头节点的指针P1，P2，如果链表中的环有n个节点，则一个指针P1指针先向前移动n步，然后两个指针以相同的速度向前移动。当P2指向指向环的入口节点时，P1已经围绕环走了一圈，又回到了入口节点。

找到环的入口这里的双指针移动可以这么理解：假如链表像图片那样链表一共有6个节点，环中有4个节点，那么不在环中的节点就是6-4=2，环的入口就知道了，是3。所以也可以不用双指针的方式，让头指针移动2步就可以到达环的入口。

对使用双指针方式的理解：环中有4个节点，先让一个节点P1移动4步，那么节点总数6-移动步数4=2，2=P1再移动2步就到入口=P2从头部移动2步到入口。

得到环中节点的数目
我们在前面提到判断一个链表是否有环时用到了一快一慢两个指针。如果两个指针相遇，则表明链表中存在环。两个指针相遇的节点一定在环中，可以从这个节点出发，一边继续向前移动一边计数，当再次回到这个节点时，就可以得到环中节点数了。

代码

ListNode类定义：

public class ListNode {
    int value;
    ListNode next = null;

    public ListNode() {
    }

    public ListNode(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "value=" + value +
                '}';
    }
}

EntryNodeOfLoop类：

public class EntryNodeOfLoop {

    public static ListNode entryNodeOfLoop(ListNode head) {
        ListNode meetingNode = meetingNode(head);
        if (meetingNode == null) {
            return null;
        }

        // 得到环中节点的数目
        int nodesInLoop = 1;
        ListNode p1 = meetingNode;
        while (p1.next != meetingNode) {
            p1 = p1.next;
            nodesInLoop++;
        }

        // 先移动p1，次数为环中节点的数目
        p1 = head;
        for(int i = 0; i < nodesInLoop; i++) {
            p1 = p1.next;
        }

        // 再移动p1和p2
        ListNode p2 = head;
        while (p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
        }

        return p1;
    }

    /**
     * 在链表中存在环的前提下找到一快一慢两个指针相遇的节点
     * @param head 头节点
     * @return 返回相遇的节点，如果不存在环那么返回null
     */
    public static ListNode meetingNode(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode slow = head.next;
        if (slow == null) {
            return null;
        }

        ListNode fast = slow.next;
        while (fast != null && slow != null) {
            // 相遇
            if (fast == slow) {
                return fast;
            }

            slow = slow.next;
            fast = fast.next;
            if (fast != null) {
                fast = fast.next;
            }
        }

        return null;
    }

    // 测试
    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(6);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        // 环
        node6.next = node3;

        System.out.println(meetingNode(node1));
    }
}