当前位置：网站首页>#yyds dry goods inventory# Interview must brush TOP101: the entry node of the ring in the linked list

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

2022-07-31 22:07: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 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.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/212/202207312137213302.html

当前位置：网站首页>#yyds dry goods inventory# Interview must brush TOP101: the entry node of the ring in the linked list

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

边栏推荐

猜你喜欢

随机推荐