#yyds dry goods inventory# Interview must brush TOP101: the entry node of the ring in the linked list

1.简述：

描述

给一个长度为n链表,若其中包含环,请找出该链表的环的入口结点,否则,返回null.

数据范围： ,

为3,所以返回结点值为3的结点.

输入描述：

输入分为2段,第一段是入环前的链表部分,第二段是链表环的部分,后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表

返回值描述：

返回链表的环的入口结点即可,我们后台程序会打印这个结点对应的结点值;若没有,则返回对应编程语言的空结点即可.

示例1

输入：

登录后复制

      
      

       
       {1,2},{3,4,5}
      
      
      
      

       
       
1.
      
      

返回值：

登录后复制

      
      

       
       3
      
      
      
      

       
       
1.
      
      

说明：

登录后复制

      
      

       
       返回环形链表入口结点,我们后台程序会打印该环形链表入口结点对应的结点值,即3
      
      
      
      

       
       
1.
      
      

示例2

输入：

登录后复制

      
      

       
       {1},{}
      
      
      
      

       
       
1.
      
      

返回值：

登录后复制

      
      

       
       "null"
      
      
      
      

       
       
1.
      
      

说明：

登录后复制

      
      

       
       没有环,返回对应编程语言的空结点,后台程序会打印"null"
      
      
      
      

       
       
1.
      
      

示例3

输入：

登录后复制

      
      

       
       {},{2}
      
      
      
      

       
       
1.
      
      

返回值：

登录后复制

      
      

       
       2
      
      
      
      

       
       
1.
      
      

说明：

登录后复制

      
      

       
       环的部分只有一个结点,所以返回该环形链表入口结点,后台程序打印该结点对应的结点值,即2
      
      
      
      

       
       
1.
      
      

​

2.代码实现：

登录后复制

      
      

       
       import java.util.*;
       
       
/*
       
       
 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) return null;
       
       
        // 定义快慢指针
       
       
        ListNode slow = pHead;
       
       
        ListNode fast = pHead;
       
       
        while(fast != null && fast.next != null){
       
       
            // Fast pointers are twice as fast as full pointers
       
       
            fast = fast.next.next;
       
       
            slow = slow.next;
       
       
            // 记录快慢指针第一次相遇的结点
       
       
            if(slow == fast) break;
       
       
        }
       
       
        // If the fast pointer points tonull,则不存在环
       
       
        if(fast == null || fast.next == null) return null;
       
       
        // 重新指向链表头部
       
       
        fast = pHead;
       
       
        // 与第一次相遇的结点相同速度出发,相遇结点为入口结点
       
       
        while(fast != slow){
       
       
            fast = fast.next;
       
       
            slow = slow.next;
       
       
        }
       
       
        return fast;
       
       
    }
       
       
}
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
       
       
6.
       
       
7.
       
       
8.
       
       
9.
       
       
10.
       
       
11.
       
       
12.
       
       
13.
       
       
14.
       
       
15.
       
       
16.
       
       
17.
       
       
18.
       
       
19.
       
       
20.
       
       
21.
       
       
22.
       
       
23.
       
       
24.
       
       
25.
       
       
26.
       
       
27.
       
       
28.
       
       
29.
       
       
30.
       
       
31.
       
       
32.
       
       
33.
       
       
34.
       
       
35.
       
       
36.
       
       
37.