【Day 11 】2024-04-18 - 142. 环形链表 II

[azl397985856]

142. 环形链表 II

入选理由

暂无

题目地址

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

前置知识

暂无

题目描述

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

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

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

进阶：

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

[zhiyuanpeng]

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        nodes = set()
        p = head
        while p:
            if p in nodes:
                return p
            nodes.add(p)
            p = p.next
        return None

Time O(N) Space O(N)

[atom-set]

• 快慢指针，快指针每次走 2 步，慢指针每次走 1 步
• 当快慢指针第一次相遇时，块指针和头结点分别走 1 步，再次相遇的节点就是环的入口节点

var detectCycle = function (head) {
  var p1 = new ListNode(0);
  var p2 = new ListNode(0);
  var ptr = new ListNode(0);
  p1.next = head;
  p2.next = head;
  ptr.next = head;

  while (p1.next && p2.next) {
    p1 = p1.next;
    p2 = p2.next ? p2.next.next : null;
    if (!p2) {
      return null;
    }

    if (p1 === p2) {
      while (ptr !== p2) {
        ptr = ptr.next;
        p2 = p2.next;
      }
      return ptr;
    }
  }
  return null;
};

复杂度分析

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

[CathyShang]

思路

• 双指针，设快慢指针 fast,slow，fast每次走2步（c++没有nullptr->next 会报错，故进行判段），slow每次走1步
• 当它们第一次相遇之后，fast回到链表头部，并每次走1步
• 当它们再次相遇时，为环形链表入口

证明：假设链表环形入口前长度L ，入口到第一次相遇点长度C，D+C=环形长度；

• 2*slow走过长度 = fast走过长度； 2(L+C)=L+D+2C； D+C 是一圈，slow被套圈了 ！
• 有上式得 L=D，所以fast和slow第二次相遇在环形入口处。

代码

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head==nullptr || head->next==nullptr || head->next->next==nullptr ) return nullptr;
        ListNode* fast = head;
        ListNode* slow = head;
        do{ 
            if(fast==nullptr) break;
            fast = fast->next;
            if(fast==nullptr) break;           
            fast = fast->next;
            slow = slow->next;
        }while(fast!=slow);  // 单独 while将多走一步
        if(fast==nullptr||slow==nullptr) return nullptr;
        fast = head;
        while(fast!=slow){
            fast = fast->next;
            slow = slow->next;
        }
        return fast;
    }
};

复杂度

• 时间$O(N)$ N 为链表长度
• 空间$O(1)$

[xil324]

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    let slow = head, fast = head;
    while(fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if(slow === fast) break;
    }
    if(!fast || !fast.next) return null;
    fast = head;
    while (slow !== fast) {
        slow = slow.next;
        fast = fast.next;
    }
    return fast; 
};

time complexity: O(n)

[lxy1108]

思路

采用快慢指针，通过是否存在交点判断是否有环；若有环再引入一个指针从头开始和慢指针一起遍历，二者交点即为环的开始点

python3代码

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

复杂度分析

空间复杂度O(1) 没有开辟额外空间 时间复杂度O(N) 因为需要遍历链表

[wwz223]

代码

var detectCycle = function (head) {
  let temp = head;
  const set = new Set();
  while (temp) {
    if (set.has(temp)) return temp;
    set.add(temp);
    temp = temp.next;
  }
  return null
};

复杂度分析

时间复杂度 O（N） 空间复杂度O（N）

[qinmengx]

// 方法2: 快慢指针法 type ListNode struct { Val int Next *ListNode }

/*1. 根据讲义内容, 假定快指针的速度是慢指针速度的2倍.

2. 第一次相遇时, 快指针走的路程为L+C+环的周长(假定环的周长为C+D) 慢指针走的路程为L+C ,即慢指针被套圈
3. 得出L=D, 此时另快指针用1倍速从链表起始位置开始走, 刚好与慢指针 剩余的路程相等, 再次相遇时, 快慢再次相遇时, 即为环形链表入口.*/

func detectCycle(head ListNode) ListNode { var fast = head var slow = head for { if fast == nil || fast.Next == nil { return nil } fast = fast.Next.Next slow = slow.Next if fast == slow { break } } fast = head for fast != slow { fast = fast.Next slow = slow.Next

}
return fast

}

[Martina001]

思路：这是个数学题 时间复杂度：On 空间复杂度O1

public ListNode detectCycle(ListNode head) {
        // 环形链表找环入口，经典公式：先fast和slow移动找到相遇点后，fast移动到链表头部，每次一步和slow同时走，再次相遇即为环入口
        ListNode fast = head;
        ListNode slow = head;
        while(true){
              if(fast == null || fast.next == null) return null;
              fast = fast.next.next;
              slow = slow.next;
              if(fast == slow) break;
        }

        fast = head;
        while(fast != slow){
            fast=fast.next;
            slow = slow.next;
        }
        return slow;
    }

[GReyQT]

题解思路：

1.，使用两个指针，一个慢指针（每次移动一步）和一个快指针（每次移动两步），同时从链表的起始位置出发。 2.，如果链表中存在环，快指针和慢指针在环内相遇。既确定链表中存在环 3，然后重新将快指针指向链表的起始位置，并且保持慢指针在相遇点。 4，最后以相同的速度（每次一步）移动慢指针和快指针。当它们再次相遇时，相遇点即为环的起始节点。 代码：

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
         ListNode *slow = head, *fast = head;
        do{
            if(!fast || !fast->next)   //不存在闭环，返回空指针
                return nullptr;
            slow = slow->next;
            fast = fast->next->next;
        }while(fast != slow);   //不相等未闭环，继续
        //存在，fast指针返回起点
        fast = head;
        //查找闭环起点，再次相交即为闭环起点
        while(fast != slow)
        {
            slow = slow->next;
            fast = fast->next;
        }
        return fast;
    }
};

复杂度分析：

• 时间复杂度：取决于链表的长度n，时间的复杂度为O(n)
• 空间复杂度：仅创建指针，因此空间复杂度为 O( 1)

[Dtjk]

class Solution: def detectCycle(self, head: ListNode) -> ListNode: fast, slow = head, head while True: if not (fast and fast.next): return fast, slow = fast.next.next, slow.next if fast == slow: break fast = head while fast != slow: fast, slow = fast.next, slow.next return fast

[smallppgirl]

思路 快慢指针

代码

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        f, s = head, head
        while True:
            if not (f and f.next): 
                return
            f, s = f.next.next, s.next
            if f == s:
                break
        f = head
        while f != s:
            f, s = f.next, s.next
        return f

时间 O(n) 空间 O(1)

[rao-qianlin]

思路：使用快慢双指针。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null){
            return null;
        }

        ListNode slow = head;
        ListNode fast = head;

        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                ListNode temp = head;
                // int i = 0;
                while(temp != slow){
                    temp = temp.next;
                    slow = slow.next;
                    // i = i+1;
                }
                return temp;
            }
        }

        return null;
    }
}

时间复杂度 O(N)

[YANGLimbo]

一开始用了笨办法，先快慢指针确定有环，再写了两层嵌套的循环，结果结果出错不知道为什么，找漏洞失败。 最后重新回归快慢指针，再次使用快慢指针找到交叉点。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        // 不知道节点可不可以指向自己，我这里按照不能做的
        // 先判断链表是否有环；如果有环，交叉点必然在head和slow中间
        if(head == nullptr || head->next == nullptr){
            return nullptr;
        }
        ListNode* fast = head;
        ListNode* slow = head;
        int flag = 0;
        while(fast!=nullptr && fast->next != nullptr){
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow){
                flag = 1;
                break;
            }
        }
        if(flag == 0){
            return nullptr;
        }
        // 当flag=1，有环，此时快指针走了2s距离，慢指针走了s距离，相遇点出发走到相遇点为s
        // 画一个示意图，设head到交叉处距离为x，则交叉处到相遇点为s-x,相遇点再走到交叉处为s-(s-x)=x
        // 所以，从head到交叉点的距离=x=相遇点到交叉点的距离
        ListNode* ptr = head;
        while(1){
            if(ptr == slow){
                break;
            }
            ptr = ptr->next;
            slow = slow->next;
        }
        return ptr;
    }
};

[YANGLimbo]

ai辅助优化后的版本，更简洁

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (head == nullptr || head->next == nullptr) {
            return nullptr;
        }

        ListNode* fast = head;
        ListNode* slow = head;
        bool hasCycle = false;

        // 第一步：使用快慢指针找到相遇点，确定是否有环
        while (fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) {
                hasCycle = true;
                break;
            }
        }

        // 如果没有环，返回null
        if (!hasCycle) {
            return nullptr;
        }

        // 第二步：找到环的入口
        // 当快慢指针首次相遇后，移动其中一个指针回到起始点，然后两个指针都以相同速度移动，
        // 当它们再次相遇时，相遇点即为环的入口。
        ListNode* ptr = head;
        while (ptr != slow) {
            ptr = ptr->next;
            slow = slow->next;
        }

        return ptr; // 此时 ptr 和 slow 相遇点即为环的入口
    }
};

AI优化后的O(n^2)时间复杂度版本，即按照原先的双层嵌套笨办法：

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast = head, *slow = head;

        // 使用快慢指针检测环
        while (fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) {  // 检测到环
                ListNode *ptr = head;
                while (true) {  // 寻找环的入口
                    ListNode *ptr1 = slow;
                    while (ptr1->next != ptr && ptr1->next != slow) {
                        ptr1 = ptr1->next;
                    }
                    if (ptr1->next == ptr) {
                        return ptr;
                    }
                    ptr = ptr->next;
                }
            }
        }
        return nullptr;
    }
};