当前位置：网站首页>＃yyds干货盘点＃面试必刷TOP101：链表中环的入口结点

＃yyds干货盘点＃面试必刷TOP101：链表中环的入口结点

2022-07-31 21:54:00 【51CTO】

1.简述：

描述

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

数据范围：，

为3，所以返回结点值为3的结点。

输入描述：

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

返回值描述：

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

示例1

输入：

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

返回值：

说明：

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

示例2

输入：

返回值：

       
       "null"
      
1.

说明：

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

示例3

输入：

返回值：

说明：

       
       环的部分只有一个结点，所以返回该环形链表入口结点，后台程序打印该结点对应的结点值，即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 = fast.next.next;
       
            slow = slow.next;
       
            // 记录快慢指针第一次相遇的结点
       
            if(slow == fast) break;
       
        }
       
        // 若是快指针指向null，则不存在环
       
        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.