链表中环的入口节点

柔光的暖阳◎ 2022-11-30 04:20 155阅读 0赞

[https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=13&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking][https_www.nowcoder.com_practice_253d2c59ec3e4bc68da16833f79a38e4_tpId_13_rp_1_ru_2Fta_2Fcoding-interviews_qru_2Fta_2Fcoding-interviews_2Fquestion-ranking]

**目录**

一、问题描述

二、代码实现

1、哈希法

2、双指针法

--------------------

## 一、问题描述 ##

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

## 二、代码实现 ##

### 1、哈希法 ###

循环遍历单链表的每个节点，

如果当前节点的地址出现在set中，则说明它是环的入口节点，直接返回

如果没有出现在set中，则将其添加到set中

当退出循环，说明链表不存在环，返回null（如果存在，在循环中就应该返回了）

/*
     public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }
    */
    import java.util.HashSet;
    public class Solution {
        
        //哈希法
        public ListNode EntryNodeOfLoop(ListNode pHead) {
            HashSet<ListNode> set = new HashSet<>();
            while (pHead != null) {
                if (set.contains(pHead)) {
                    return pHead;
                }
                
                set.add(pHead);
                pHead = pHead.next;
            }
            return null;
        }
    }

### 2、双指针法 ###

第一步，让快慢指针均指向头节点，然后fast指针一次走两步，slow指针一次走一步。如果期间fast变为null或者fast.next变为null，说明链表不存在环，直接返回null。如果期间存在fast == slow，说明链表存在环，并记此时的节点为快慢指针第一次相遇的节点p。

第二步，让slow指针重新指向头节点、fast原地不动，然后让slow指针、fast指针每次走一步，则它们再次相遇的地方，就是环的入口节点q。

证明：在第一步中，由于快指针的速度是慢指针的两倍，并且它们在p点相遇，则2(a + b) = a + (n-1)b + (n-1)c + b，则a = (n-2)b + (n-2)c + c，所以当slow指针走a步时，fast走了(n-2)b + (n-2)c + c步，正好走到q点，与slow指针碰面，而这个q点正好是环的入口点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzMwOTczNDMx_size_16_color_FFFFFF_t_70][]

/*
     public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }
    */
    public class Solution {
    
        //双指针法
        public ListNode EntryNodeOfLoop(ListNode pHead)
        {
            //1、判断是否有环
            ListNode slow = pHead, fast = pHead;
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
                
                if (slow == fast) {
                    break;
                }
            }
            
            //不存在环
            if (fast == null || fast.next == null) {
                return null;
            }
            //存在环
            //2、找到环的入口节点
            slow = pHead;
            while (slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    }

参考：

[https://leetcode.com/problems/linked-list-cycle-ii/discuss/44774/Java-O(1)-space-solution-with-detailed-explanation][https_leetcode.com_problems_linked-list-cycle-ii_discuss_44774_Java-O_1_-space-solution-with-detailed-explanation]

[https://www.nowcoder.com/questionTerminal/253d2c59ec3e4bc68da16833f79a38e4?answerType=1&f=discussion][https_www.nowcoder.com_questionTerminal_253d2c59ec3e4bc68da16833f79a38e4_answerType_1_f_discussion]

[https_www.nowcoder.com_practice_253d2c59ec3e4bc68da16833f79a38e4_tpId_13_rp_1_ru_2Fta_2Fcoding-interviews_qru_2Fta_2Fcoding-interviews_2Fquestion-ranking]: https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=13&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzMwOTczNDMx_size_16_color_FFFFFF_t_70]: /images/20221124/6b2f1d30027b4475b0b24027ba34015e.png
[https_leetcode.com_problems_linked-list-cycle-ii_discuss_44774_Java-O_1_-space-solution-with-detailed-explanation]: https://leetcode.com/problems/linked-list-cycle-ii/discuss/44774/Java-O%281%29-space-solution-with-detailed-explanation
[https_www.nowcoder.com_questionTerminal_253d2c59ec3e4bc68da16833f79a38e4_answerType_1_f_discussion]: https://www.nowcoder.com/questionTerminal/253d2c59ec3e4bc68da16833f79a38e4?answerType=1&f=discussion