【Day 11 】2024-08-25 - 142. 环形链表 II

[azl397985856]

142. 环形链表 II

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/linked-list-cycle-ii/

前置知识

暂无

题目描述

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

进阶：

你是否可以使用 O(1) 空间解决此题？

[Fightforcoding]

Approach

First using slow and fast pointers to detect whether there is a cycle in the linked list then find the cycle start by using another pointer from the head of the list to find the start point.

Code

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow_ptr = head
        fast_ptr = head
        new_head = head
        while fast_ptr and fast_ptr.next:
            slow_ptr = slow_ptr.next
            fast_ptr = fast_ptr.next.next
            if slow_ptr == fast_ptr:
                while new_head != slow_ptr:
                    slow_ptr = slow_ptr.next
                    new_head = new_head.next
                return new_head

        return None

Time complexity O(n)

Space complexity O(1)

[CelesteXiong]

Intuition

Use a faster point and a slower point starting in the head. The faster pointer walked twice as fast as the slower pointer. Assuming that a is the length of the head to the entrance of the circle, and b is the length of the entrance to the first meet point, and c is the length of the circle. When they first met, the faster pointer walked $(a + b + kc)$, and the slower pointer walked $(a+b)$, so we got (a+b+kc) = 2(a+b), where we can obtain the a = kc - b. Then we move the faster pointer back into the head, and walked in the same speed as the slower pointer. Once they met, we got the entrance to the circle.

Algorithm

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow, fast = head, head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next 
            if slow == fast: break
        if not fast or not fast.next: return None
        fast = head
        while slow and fast:
            if fast == slow: return fast
            fast = fast.next 
            slow = slow.next 
        return None

Complexity

Time: O(n), n is the length of linked list

Space: O(1)

[peggyhao]

public class Solution {
    public ListNode detectCycle(ListNode head) {
         if (head == null) {
            return null;
         }
         ListNode slow = head, fast = head;
         while (fast != null) {
            slow = slow.next;
            if (fast.next != null) {
                fast = fast.next.next;
            } else {
                return null;
            }
            if (fast == slow) {
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
         }
         return null;
    }

}

time: O(n) space: O(1)

[huizsh]

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        visited = set()
        pos = head
        while pos:
            if pos in visited:
                return pos
            visited.add(pos)
            pos = pos.next
        return None

The detectCycle method checks for a cycle in a linked list. It keeps track of visited nodes using a set (visited), and if a node is revisited, it returns that node, indicating the start of the cycle. If no cycle is found, the method returns None.

[sleepydog25]

Approach

Answer 1:

1. Create a set
2. Store the nodes you've been through in the set

Answer 2:

Floyd's Cycle Detection Algorithm

1. make two pointer fast and slow
2. when fast and slow meets, indicates there is a cycle
3. make a third pointer "start", that starts from head and slow will loop through the cycle
4. at the end start and slow will meet each other

Algorithm

Answer 1:

1. Also passed leetcode 141

   /**
   * Definition for singly-linked list.
   * class ListNode {
   *     int val;
   *     ListNode next;
   *     ListNode(int x) {
   *         val = x;
   *         next = null;
   *     }
   * }
   */
   public class Solution {
   public ListNode detectCycle(ListNode head) {
         if (head == null)
           return null;
   
       HashSet <ListNode> store = new HashSet <ListNode> ();
       ListNode pointer = head;
   
       while (pointer != null){
           if (store.contains(pointer)){
               return pointer;
           }
           store.add(pointer);
           pointer = pointer.next;
       }
       return null;
   }
   }

Answer 2:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {

         if (head == null|| head.next == null)
          return null;

        ListNode slow = head;
        ListNode fast = head;

        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast){ // the cycle exists

                ListNode start = head; // tell me where the cycle starts

                while(start != slow){
                    slow = slow.next;
                    head = head.next;
                }
                return start;
            }
        }
        return null; //no cycle
    }
}

Complexity

Answer1:

1. Time Complexity:O(n)
2. Space Complexity:O(n)

   Answer2:

3. Time Complexity:O(n)
4. Space Complexity:O(1)

[zjy-debug]

思路

使用两个指针，一个快指针和一个慢指针，快指针每次移动两步，慢指针每次移动一步。如果链表中存在环，两个指针最终会相遇。

代码

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None

        slow = head
        fast = head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

            if slow == fast:
                break
        else:
            return None

        entry = head
        while entry != slow:
            entry = entry.next
            slow = slow.next

        return entry

复杂度

时间复杂度：O(N)

空间复杂度：O(1)

[akxuan]

   node_dict = set()

        while head:
            if head in node_dict:
                return head 
            else:
                node_dict.add(head)
                head = head.next

        return None

先放一个时空复杂度都是 O(N) 的

终于弄明白这个题了， 弄明白了就很简单。 有三个段， a， b， c。 a: 是从起点到环入口 b: 是从环入口到交点 c: 是从交点到环入口

等于 b + c 就是环。 由于 fast 走过了两倍的 slow。 2*(a+b) = a + n(b + c)
一番变换： a = c + (n-1)(b+c)

所以， 我们希望找到环入口的话， 让一个node 从起点走完a， 就等于 slow 继续从相遇点， 绕 n-1 圈之后再走完c。 纠结这个n-1 的value ， 其实不管绕几圈， 我只是希望他俩同时到达入口而已， 就是希望走完c。

        fast = slow = head
        has_cycle = False 
        while fast and fast.next and fast.next.next: 
            slow = slow.next
            fast = fast.next.next

            if slow == fast: 
                 has_cycle = True 
                 break

        if has_cycle:
            new = head
            while new != slow: 
                new = new.next
                slow = slow.next
            return new

        else:
            return None  

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

[godkun]

思路

数据结构：环形链表

实现思路：用了快慢指针判断是否有环，如果相遇则在环中。但是没有get到 将 slow 指针重新指向链表的头节点，然后 slow 和 fast 每次各移动一步，直到它们再次相遇，相遇点即为环的起始节点。这个逻辑，学习到了。

代码

TS实现

function detectCycle(head: ListNode | null): ListNode | null {
  if (head === null) return null
  let slow = head
  let fast = head

  while (fast !== null && fast.next !== null) {
    slow = slow.next
    fast = fast.next.next
    if (slow === fast) {
      slow = head
      while (slow !== fast) {
        slow = slow.next
        fast = fast.next
      }
      return slow
    }
  }
  return null
}

复杂度分析

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