leetcode 142. Linked List Cycle II

深藏阁楼爱情的钟 2023-07-13 03:23 10阅读 0赞

**目录**

一、问题描述

二、代码实现

1、使用Set

2、双指针法（快慢指针）

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

[https://leetcode.com/problems/linked-list-cycle-ii/][https_leetcode.com_problems_linked-list-cycle-ii]

给定一个可能存在环的链表，返回链表中环的入口点。要求空间复杂度为O(1)，同时注意不能改动链表。

## 一、问题描述 ##

测试用例：

**Example 1:**

Input: head = [3,2,0,-4], pos = 1
    Output: true
    Explanation: There is a cycle in the linked list, where tail connects to the second node.

![format_png][]

**Example 2:**

Input: head = [1,2], pos = 0
    Output: true
    Explanation: There is a cycle in the linked list, where tail connects to the first node.

![format_png 1][]

**Example 3:**

Input: head = [1], pos = -1
    Output: false
    Explanation: There is no cycle in the linked list.

![format_png 2][]

pos为0、1表示环的入口点是第一个元素、第二个元素，pos为-1表示单链表不存在环。

## 二、代码实现 ##

### 1、使用Set ###

### 2、双指针法（快慢指针） ###

/**
     * Definition for singly-linked list.
     * class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    public class Solution {
        
        public ListNode detectCycle2(ListNode head) {
            if (head == null || head.next == null) {
                return null;
            }
            
            //1、找到快慢指针第一次相遇的节点（即，判断单链表是否存在环）
            //ListNode slow = head, fast = head.next.next; //Time Limit Exceeded
            ListNode slow = head, fast = head;
            ListNode pos = null;
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
                
                if (slow == fast) {
                    //return slow;    
                    //slow是第一次相遇点，但第一次相遇点可能不是入环点
                    pos = slow;
                    break;
                }
            }
            
            
            //pos != null  环存在
            if (pos != null) {
                //2、找到快慢指针再次相遇的节点（即，找到环的入口点）
                slow = head;
                /*
                //[1,2] 0   输出tail connects to node index 1    期待tail connects to node index 0
                while (fast != null && fast.next != null) {
                    fast = fast.next;
                    slow = slow.next;
                    
                    if (slow == fast) {
                        return slow;
                    }
                }
                */
                /*
                HashSet<ListNode> set = new HashSet<>();
                ListNode cur = head;
                while (cur != null) {
                    if (!set.contains(cur)) {
                        set.add(cur);
                    } else {
                        return cur;
                    }
                    
                    cur = cur.next;
                }
                */
                
                //while (fast != null && fast.next != null) {
                while (fast != null) {
                    if (slow == fast) {
                        return slow;
                    }
                    
                    fast = fast.next;
                    slow = slow.next;
                }
                            
            }
            
            //pos = null;  环不存在
            return null;
        }
         
        public ListNode detectCycle_error(ListNode head) {
            if (head == null) {
                return head;    //return null <-> no cycle
            }
            
            //1、找到快慢指针第一次相遇的节点（即，判断单链表是否存在环）
            ListNode slow = head, fast = head;
            while (fast.next != null && fast.next.next != null) {
                slow = slow.next;
                fast = fast.next.next;
                
                if (slow == fast) { //第一次相遇的节点
                    break;
                }
            }
            
            //if (slow != fast) { //即，fast.next == null
            //if (fast.next == null) {
            //[1,2] -1  输出tail connects to node index 0  期待no cycle
            if (fast == null || fast.next == null) {
                return null;
            }
            
            //2、找到快慢指针再次相遇的节点（即，找到环的入口点）
            slow = head;
            fast = fast;
            //while (slow != fast) {  //由于存在环，肯定不会走到null，因此这里不加上判断null应该也没问题
            //[1] -1   输出tail connects 头node index 0   期待no cycle
            // while (fast.next != null) {
            //     slow = slow.next;
            //     fast = fast.next;
            //     if (slow == fast) {
            //         break;
            //     }
            // }
            //[1,2] 0   输出tail connects to node index 1    期待tail connects to node index 0
            while (fast.next != null) {
                if (slow == fast) {
                    break;
                }
                
                slow = slow.next;
                fast = fast.next;
            }
            //[1] -1    输出tail connects to node index 0 期待no cycle
            
            return slow;
        }
        
    }

参考：

[https://leetcode.com/problems/linked-list-cycle-ii/discuss/44781/Concise-O(n)-solution-by-using-C%2B%2B-with-Detailed-Alogrithm-Description][https_leetcode.com_problems_linked-list-cycle-ii_discuss_44781_Concise-O_n_-solution-by-using-C_2B_2B-with-Detailed-Alogrithm-Description]

[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://leetcode.com/problems/linked-list-cycle-ii/discuss/44793/O(n)-solution-by-using-two-pointers-without-change-anything][https_leetcode.com_problems_linked-list-cycle-ii_discuss_44793_O_n_-solution-by-using-two-pointers-without-change-anything]

[https://leetcode.com/problems/linked-list-cycle-ii/discuss/44915/Java-two-pointers-solution][https_leetcode.com_problems_linked-list-cycle-ii_discuss_44915_Java-two-pointers-solution]

[https://leetcode.com/problems/linked-list-cycle-ii/discuss/44822/Java-two-pointer-solution.][https_leetcode.com_problems_linked-list-cycle-ii_discuss_44822_Java-two-pointer-solution.]

[https://leetcode.com/problems/linked-list-cycle-ii/discuss/44777/Concise-JAVA-solution-based-on-slow-fast-pointers][https_leetcode.com_problems_linked-list-cycle-ii_discuss_44777_Concise-JAVA-solution-based-on-slow-fast-pointers]

[https://leetcode.com/problems/linked-list-cycle-ii/discuss/44893/My-two-cents-still-O(1)-memory-and-O(n)-time][https_leetcode.com_problems_linked-list-cycle-ii_discuss_44893_My-two-cents-still-O_1_-memory-and-O_n_-time]

[https://leetcode.com/problems/linked-list-cycle-ii/discuss/44902/Sharing-my-Python-solution][https_leetcode.com_problems_linked-list-cycle-ii_discuss_44902_Sharing-my-Python-solution]

[https://leetcode.com/problems/linked-list-cycle-ii/discuss/44929/Share-my-O(n)-complexity-and-constant-space-code.-Keep-the-original-list.-Any-comments.][https_leetcode.com_problems_linked-list-cycle-ii_discuss_44929_Share-my-O_n_-complexity-and-constant-space-code.-Keep-the-original-list.-Any-comments.]

[https_leetcode.com_problems_linked-list-cycle-ii]: https://leetcode.com/problems/linked-list-cycle-ii/
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9hc3NldHMubGVldGNvZGUuY29tL3VwbG9hZHMvMjAxOC8xMi8wNy9jaXJjdWxhcmxpbmtlZGxpc3QucG5n?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9hc3NldHMubGVldGNvZGUuY29tL3VwbG9hZHMvMjAxOC8xMi8wNy9jaXJjdWxhcmxpbmtlZGxpc3RfdGVzdDIucG5n?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9hc3NldHMubGVldGNvZGUuY29tL3VwbG9hZHMvMjAxOC8xMi8wNy9jaXJjdWxhcmxpbmtlZGxpc3RfdGVzdDMucG5n?x-oss-process=image/format,png
[https_leetcode.com_problems_linked-list-cycle-ii_discuss_44781_Concise-O_n_-solution-by-using-C_2B_2B-with-Detailed-Alogrithm-Description]: https://leetcode.com/problems/linked-list-cycle-ii/discuss/44781/Concise-O%28n%29-solution-by-using-C%2B%2B-with-Detailed-Alogrithm-Description
[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_leetcode.com_problems_linked-list-cycle-ii_discuss_44793_O_n_-solution-by-using-two-pointers-without-change-anything]: https://leetcode.com/problems/linked-list-cycle-ii/discuss/44793/O%28n%29-solution-by-using-two-pointers-without-change-anything
[https_leetcode.com_problems_linked-list-cycle-ii_discuss_44915_Java-two-pointers-solution]: https://leetcode.com/problems/linked-list-cycle-ii/discuss/44915/Java-two-pointers-solution
[https_leetcode.com_problems_linked-list-cycle-ii_discuss_44822_Java-two-pointer-solution.]: https://leetcode.com/problems/linked-list-cycle-ii/discuss/44822/Java-two-pointer-solution.
[https_leetcode.com_problems_linked-list-cycle-ii_discuss_44777_Concise-JAVA-solution-based-on-slow-fast-pointers]: https://leetcode.com/problems/linked-list-cycle-ii/discuss/44777/Concise-JAVA-solution-based-on-slow-fast-pointers
[https_leetcode.com_problems_linked-list-cycle-ii_discuss_44893_My-two-cents-still-O_1_-memory-and-O_n_-time]: https://leetcode.com/problems/linked-list-cycle-ii/discuss/44893/My-two-cents-still-O%281%29-memory-and-O%28n%29-time
[https_leetcode.com_problems_linked-list-cycle-ii_discuss_44902_Sharing-my-Python-solution]: https://leetcode.com/problems/linked-list-cycle-ii/discuss/44902/Sharing-my-Python-solution
[https_leetcode.com_problems_linked-list-cycle-ii_discuss_44929_Share-my-O_n_-complexity-and-constant-space-code.-Keep-the-original-list.-Any-comments.]: https://leetcode.com/problems/linked-list-cycle-ii/discuss/44929/Share-my-O%28n%29-complexity-and-constant-space-code.-Keep-the-original-list.-Any-comments.