[Leetcode][第141、142题][JAVA][环形链表][哈希表][快慢指针][数学推理]

梦里梦外; 2022-12-13 12:46 130阅读 0赞

#### 【问题描述】\[中等\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]

#### 【解答思路】 ####

### 141 ###

每次遍历到一个节点时，判断该节点此前是否被访问过。

具体地，我们可以使用哈希表来存储所有已经访问过的节点。每次我们到达一个节点，如果该节点已经存在于哈希表中，则说明该链表是环形链表，否则就将该节点加入哈希表中。重复这一过程，直到我们遍历完整个链表即可。

###### 1. 哈希表 ######

**时间复杂度：O(N) 空间复杂度：O(N)**

public class Solution { 
        public boolean hasCycle(ListNode head) { 
            Set<ListNode> seen = new HashSet<ListNode>();
            while (head != null) { 
                if (!seen.add(head)) { 
                    return true;
                }
                head = head.next;
            }
            return false;
        }
    }

###### 2. 快慢指针 ######

快指针走两步 慢指针走一步 如果有环 终有一天会追上  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 3]

**时间复杂度：O(N) 空间复杂度：O(1)**

public boolean hasCycle(ListNode head) { 
            ListNode slow = head;
            ListNode fast = head;
            while(fast!=null && fast.next!=null){ 
                slow=slow.next;
                fast=fast.next.next;
                if(slow==fast){ 
                    return true;
                }
            }
            return false;
        }

### 142 ###

###### 1. 哈希表 ######

**时间复杂度：O(N) 空间复杂度：O(N)**

public class Solution { 
        public ListNode detectCycle(ListNode head) { 
            ListNode pos = head;
            Set<ListNode> visited = new HashSet<ListNode>();
            while (pos != null) { 
                if (visited.contains(pos)) { 
                    return pos;
                } else { 
                    visited.add(pos);
                }
                pos = pos.next;
            }
            return null;
        }
    }

###### 2. 快慢指针 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 6]

**时间复杂度：O(N) 空间复杂度：O(1)**

public class Solution { 
        //如果链表有环，请找到环的入口点
    //fast一次走两步，slow一次走一步。所以，相遇的时候，fast所走的路程是slow所走的路程的两倍
    //设起始位置到环入口点的距离为X，入口点到第一次相遇的位置的距离为L，C代表环的长度。
    //slow和fast第一次相遇时，slow：X+L； fast：X+L+NC (N指代圈次)。
    // 由上推出： 2(X+L) = X+L+NC -> X = NC - L;和圈数(环数)无关 -> X = C - L;
    // 由上可得：当slow和fast第一次相遇时，把slow放到链表头部，与fast一起走，直到再次相遇，
    // 那么这个相遇点就是环的入口点。
    
    //X = C - L
    
        public ListNode detectCycle(ListNode head) { 
             if(head == null || head.next ==null) return null;
    			ListNode fast = head ;
    			ListNode slow = head ;
    			while(fast != null && fast.next != null) { 
    				slow =slow.next;
    				fast = fast.next.next;
    				 if (fast == slow) { 
                        slow = head;
                        while (fast != slow) { 
                            fast = fast.next;
                            slow = slow.next;
                        }
                        return slow;
                    }
                }
    			return null;
        }
        
    }

#### 【总结】 ####

###### 1. 环形链表思路 快慢指针 哈希表 ######

###### 2.快慢指针 ######

链表常用技巧 快的走两步 慢的走一步

参考链接：  
https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/linked-list-cycle-ii-kuai-man-zhi-zhen-shuang-zhi-/  
参考链接：  
https://leetcode-cn.com/problems/linked-list-cycle/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/ceda9f905ee649e4b9d9575b1caba9b2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/ce00ee366d02456da1b4657864d4651c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/91e5dddcf5e0438b985e1cedb2588418.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/59b2ffcb10ed4b2191a1f69d17780588.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/181dfeb217434a1989a4d6ce5bfd0d9b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/3e6a43fd957549608e799db4e56ab330.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221123/04543c0eb66642bc8ccdc881a63d5b21.png