牛客在线编程101-7 链表中环的入口结点

Love The Way You Lie 2023-10-04 19:43 3阅读 0赞

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

数据范围： n\\le10000n≤10000，1<=结点值<=100001<=结点值<=10000  
要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

例如，输入\{1,2\},\{3,4,5\}时，对应的环形链表如下图所示：

可以看到环的入口结点的结点值为3，所以返回结点值为3的结点。  
输入描述：  
输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表  
返回值描述：  
返回链表的环的入口结点即可，我们后台程序会打印这个结点对应的结点值；若没有，则返回对应编程语言的空结点即可。  
解析  
[牛客网解析][Link 1]  
双指针

/*
     public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }
    */
    public class Solution {
        
        public ListNode EntryNodeOfLoop(ListNode pHead) {
        
            //快慢指针
            ListNode slow = pHead;
            ListNode fast = pHead;
            while(fast != null && fast.next != null) {
        
                fast = fast.next.next;
                slow = slow.next;
                //有环，找到相遇点
                if (slow == fast) {
        
                    //两个指针同时走，相遇点就是环起始点
                    fast = pHead;
                    while(fast != null) {
        
                        if (slow == fast) {
        
                            return slow;
                        }
                        fast = fast.next;
                        slow = slow.next;
                    }
                }
            }
            return null;
        }
    }

[Link 1]: https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=295&tqId=23449&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=/exam/oj