链表中环的入口节点

缺乏、安全感 2022-05-14 03:56 135阅读 0赞

## 问题描述 ##

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

有环链表类似于下图中的链表：

![70][]

可以看到该链表中有一个环，其中橙色的节点就是这个链表中环的入口节点。

解决这个问题可以分三步。

（1）第一步是确定一个链表中是否包含环。我们可以用两个指针来解决这个问题。定义两个指针，同时从链表的头结点出发，一个指针一次走一步，另一个指针一次走两步。如果走得快的指针追上了走得慢的指针，那么链表就包含环；吐过走得快得快的指针走到了链表的末尾（ListNode的next指向null）都没有追上第一个指针，那么链表就不包含环。

（2）第二步是找到环中节点的数目，这一步的目的就是为寻找环的入口做铺垫。我们在上面提到判断一个链表里面是否有环时用到了一快一慢两个指针。如果两个指针相遇，则表明链表中存在环。两个指针相遇的节点一定是在环中。可以从这个节点出发，一边继续向前移动一边计数，当再次回到这个节点时，就可以得到环中节点数了。

（3）第三步是找到环的入口。我们还可以利用两个指针来解决这个问题。先定义两个指针P1和P2指向链表的头结点。如果链表中的环有n个节点，则指针P1先在链表上向前移动n步，然后两个指针以相同的速度向前移动。当第二个指针指向环的入口节点时，第一个指针已经围绕着环走了一圈，又回到了入口节点。

有了上面的分析过程，我们就可以写代码实现这个算法了：

其中使用到的链表的数据结构如下：

public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }

其中测试的链表的结构如下：

![70 1][]

查找链表中环的入口节点的代码：

public class Solution {
    
        public static void main(String[] args) {
            //构造链表结构测试用
            ListNode a = new ListNode(1);
            ListNode b = new ListNode(2);
            ListNode c = new ListNode(3);
            ListNode d = new ListNode(4);
            ListNode e = new ListNode(5);
            ListNode f = new ListNode(6);
            a.next = b;
            b.next = c;
            c.next = d;
            d.next = e;
            e.next = f;
            f.next = c;
    
            Long begintime = System.nanoTime();
            ListNode result =  EntryNodeOfLoop(a);
            Long endtime = System.nanoTime();
            if(result!=null){
                System.out.println("链表的入环节点为："+result.val+",运行时间："+(endtime - begintime) + "ns");
            }else{
                System.out.println("该链表中没有环");
            }
    
        }
    
        //两个指针相遇的节点
        public static ListNode MeetingNode(ListNode pHead) {
            ListNode p = pHead;
            ListNode q = pHead;
            ListNode meet = null;
            while(p!=null && q!=null){
               p = p.next;
               q = q.next.next;
               if(p!=null && q!=null && p.val == q.val){
                   meet = p;
                   return meet;
               }
            }
            return meet;
    
        }
        //环的入口节点
        public static ListNode EntryNodeOfLoop(ListNode pHead) {
            ListNode meetingNode = MeetingNode(pHead);
            System.out.println("在环中相遇的节点为："+meetingNode.val);
            ListNode pNode1 = pHead;
            ListNode pNode2 = pHead;
            ListNode loopnode = null;
            if(meetingNode==null){
                return loopnode;
            }
            //得到环中节点的数目
            int nodeInLoop = 1;
            ListNode temp = meetingNode;
            while(temp.next!=meetingNode){
                temp = temp.next;
                nodeInLoop++;
            }
            System.out.println("环中节点的数目为："+nodeInLoop+"个");
           //先移动pNode1,次数为环中节点的数目
            pNode1 = pHead;
            for(int i = 0;i < nodeInLoop;i++){
                pNode1 = pNode1.next;
            }
            //再移动pNode1和pNode2
            while(pNode1!=pNode2){
                pNode1 = pNode1.next;
                pNode2 = pNode2.next;
            }
            return pNode1;
        }
     
    }

程序运行结果：

![70 2][]

该算法的时间复杂度为**O(n)**。

[70]: /images/20220514/481e75cd6c8945ef855b74cfec203c61.png
[70 1]: /images/20220514/ac25872f889d47fc863cc5b7976b6809.png
[70 2]: /images/20220514/00517f26c9a843058186e08740d7a394.png