【Day 11 】2023-06-20 - 142. 环形链表 II

[azl397985856]

142. 环形链表 II

入选理由

暂无

题目地址

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

前置知识

暂无

题目描述

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

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

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

进阶：

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

[bi9potato]

Approach

Fast and Slow Pointers

Code

/**
 * 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) {

        ListNode pSlow = head;
        ListNode pFast = head;

        while (pFast != null && pFast.next != null ) {
            pSlow = pSlow.next;
            pFast = pFast.next.next;

            if (pFast == pSlow) break;
        }

        if (pFast == null || pFast.next == null) {
            return null;
        }

        pSlow = head;
        while (pSlow != pFast) {
            pSlow = pSlow.next;
            pFast = pFast.next;
        }

        return pSlow;

    }
}

Complexity Analysis

• Time $\mathcal{O}(N)$
• Spce $\mathcal{O}(1)$

[zhaoygcq]

思路

使用一个Map来记录已经遍历过的节点，如果在遍历过程中，又遇到了之前遍历的节点，那就认为该节点为环形链表的头节点。

代码

var detectCycle = function(head) {
    let map = new WeakMap();
    let curr = head;
    while(curr) {
        if(!map.has(curr)) {
            map.set(curr, 1);
        } else {
            return curr;
        }
        curr = curr.next;
    }
    return null;
};

复杂度分析

• 时间复杂度：O(N)，其中 N 为数组长度。
• 空间复杂度：O(N)

[hengistchan]

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        while(head) {
            if(!less<ListNode *>()(head, head->next)) {
                return head->next;
            }
            head = head->next;
        }
        return nullptr;
    }
};

[RocJeMaintiendrai]

public class Solution { public ListNode detectCycle(ListNode head) { ListNode slow = head, fast = head; 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; } while(head != slow) { head = head.next; slow = slow.next; } return head; } }

[RanDong22]

typescript

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function detectCycle(head: ListNode | null): ListNode | null {
  const retNode = new ListNode();
  retNode.next = head;
  let front = retNode,
    end = retNode;
  while (end && end.next) {
    front = front.next!;
    end = end.next?.next!;
    if (front === end) {
      break;
    }
  }
  if (!end || !end.next) {
    return null;
  }
  front = retNode;
  while (front !== end) {
    front = front.next!;
    end = end.next!;
  }
  return end;
}

[catkathy]

思路

快慢指针

Code

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow, fast = head, head

        # find the meeting point
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            # if found, break the loop
            if slow == fast:
                break
            # if not, return null
        else:
            return None

        # Find the node where the cycle begins
        # Move the slow pointer to the head of the linked list
        slow = head

        while slow != fast:
            slow = slow.next
            fast = fast.next
        return fast # or return slow (starting point)

        # Move both pointers at the same pace until they meet again

[GuitarYs]

···python class Solution(object): def detectCycle(self, head): """ :type head: ListNode :rtype: ListNode """ if not head or not head.next: return None

    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break

    if not fast or not fast.next:
        return None

    ptr1, ptr2 = head, fast
    while ptr1 != ptr2:
        ptr1 = ptr1.next
        ptr2 = ptr2.next

    return ptr1

···

[zcytm3000]

class Solution(object): def detectCycle(self, head): 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

[Diana21170648]

思路

法一遍历链表，用哈希表存节点，第一次遍历两次的节点就是环的入口 法二用双指针，快走两步，慢走一步，如果慢=快，证明有环，慢从头开始，快从相遇点开始，下次相遇点即为环的入口 以下内容使用法二

代码

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

复杂度分析

• 时间复杂度：O(N)，其中 N 为链表的长度。
• 空间复杂度：O(1)，使用快慢指针，未占用其它空间

[Xinyue-Ma]

class Solution(object):
    def detectCycle(self, head):
        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

[passengersa]

思路： 定义快指针 fast 和慢指针 slow，初始时都指向链表头节点。 快指针每次向后移动2个节点，慢指针每次向后移动1个节点，直到快指针或者慢指针到达链表尾部。 如果链表无环，则返回null。 如果链表有环，则快指针和慢指针必定会在环内相遇。 当快指针和慢指针相遇时，将快指针重新指向链表头节点，然后快指针和慢指针都每次向后移动1个节点，直到它们再次相遇，相遇的节点即为环的入口节点。 代码： /**

• @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) { fast = head; while (fast !== slow) { fast = fast.next; slow = slow.next; } return fast; } } return null; }; 复杂度分析 时间复杂度：O(N)，其中 N 为链表的长度。 空间复杂度：O(1)，使用快慢指针，未占用其它空间

[C2tr]

class Solution { public: ListNode detectCycle(ListNode head) { while(head) { if(!less<ListNode *>()(head, head->next)) { return head->next; } head = head->next; } return nullptr; } };

[yetfan]

代码

class Solution(object):
    def detectCycle(self, head):
        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

[SoSo1105]

思路

使用额外的数组存储已访问过的节点，当某时刻访问时判断当前节点的next是否已出现过

代码

# 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]:
        if not head: return None

        res = []
        while head.next:
            if head.next in res:
                return res[res.index(head.next)]
            res.append(head)
            head = head.next

        return None

复杂度分析

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

[RestlessBreeze]

code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (!head || !head->next)
            return nullptr;
        ListNode* s = head;
        ListNode* f = head;
        while (f && f->next)
        {
            s = s->next;
            f = f->next->next;
            if (s == f)
                break;
        }
        if (f == nullptr || f->next == nullptr)
            return nullptr;
        f = head;
        while (f != s)
        {
            s = s->next;
            f = f->next;
        }
        return f;
    }
};

[SunStrongChina]

思路

将每一个节点存入到字典中，如果某个节点再次出现时，就是环开始的地方

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dict1 = {}
        i = 0
        while head:
            i = 0 
            if head in dict1.keys():
                return head
            else:
                dict1[head] =  i
            i += 1
            head = head.next
        return head

时间复杂度O(n)

空间复杂度O(n)

[mo660]

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slowPtr = head;
        ListNode *fastPtr = head;
        while(1){
            if (nullptr == fastPtr || nullptr == fastPtr->next) return nullptr;
            slowPtr = slowPtr->next;
            fastPtr = fastPtr->next->next;
            if (slowPtr == fastPtr) break;
        }
        fastPtr = head;
        while(fastPtr != slowPtr){
            slowPtr = slowPtr->next;
            fastPtr = fastPtr->next;
        }
        return fastPtr;
    }
};

[Alexno1no2]

class Solution(object):
    def detectCycle(self, head):
        fast, slow = head, head
        while True:
            if not fast or not fast.next: 
                return # 没有环 会走到最后
            fast, slow = fast.next.next, slow.next
            if fast == slow:  # 环中第一次相遇
                break

        '''
        设链表分为两段，环形入口前的一段为a，环形长度为b，链表总共有a + b ,设第一次相遇时fast走了f，slow走了s，则 f = 2s ，设f比s夺走了 nb（环形的倍数），则 f - s = nb，
        则 s = nb ， f = 2nb；
        假设指针从链表头部一直向前走k步，可以走到环形入口，则 k = a + mb（m=0,1,2，……），slow已经走了nb步，则slow再走a步就肯定可以走到环形入口  
        '''
        fast = head
        while fast != slow:
            fast, slow = fast.next, slow.next
        return fast

[Fuku-L]

代码

/**
 * 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) {
            ListNode p1 = head, p2 = head;
            while (true) {
                if (p2 == null || p2.next == null) {
                    return null;
                }
                p1 = p1.next;
                p2 = p2.next.next;
                if (p1 == p2) {
                    break;
                }
            }
            p2 = head;
            while (p1 != p2) {
                p1 = p1.next;
                p2 = p2.next;
            }
            return p1;
        }
}

[61hhh]

代码

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (true) {
            // 没环时fast先结束 fast速度为2 要判断fast和fast.next 避免NPE
            if (fast == null || fast.next == null) {
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;
            // 相遇时退出循环
            if (fast == slow) {
                break;
            }
        }
        // 重置slow到起点 同速度前进
        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}

复杂度分析 ● 时间复杂度：O(n) ● 空间复杂度：O(1)

[kingxiaozhe]

function ListNode(val) {
  this.val = val;
  this.next = null;
}

function detectCycle(head) {
  if (head === null || head.next === null) {
    return null;
  }

  let slow = head;
  let fast = head;
  let hasCycle = false;

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

    if (slow === fast) {
      hasCycle = true;
      break;
    }
  }

  if (!hasCycle) {
    return null;
  }

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

  return slow;
}

[yzhyzhyzh123]

思路

快慢指针

代码

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = 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;
    }
}

复杂度

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

[acy925]

思路

快慢指针

代码

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

        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if fast == slow:
                break
        if fast is None or fast.next is None:
            return None

        slow = head
        while slow != fast:
            fast = fast.next
            slow = slow.next
        return slow

复杂度分析

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

[snmyj]

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {

        ListNode *f,*s,*prev;
        prev=new ListNode(-1);
        prev->next=head;
        f=prev,s=prev;
        while(1){
               if(f->next==nullptr||f->next->next==nullptr) return nullptr;
               else {
                   f=f->next->next;
                   s=s->next;
               }
               if(f==s){
                   f==prev;
                   break;
               }
        }
        while(s!=f){
            f=f->next;
            s=s->next;

        }
         return f;
    }
};

[joemonkeylee]

function detectCycle(head: ListNode | null): ListNode | null {
    const visited = new Set();
    while (head !== null) {
        if (visited.has(head)) {
            return head;
        }
        visited.add(head);
        head = head.next;
    }
    return null;
};

[Hughlin07]

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;
}

}

[Beanza]

思路

使用一个Map来记录已经遍历过的节点，如果在遍历过程中，又遇到了之前遍历的节点，那就认为该节点为环形链表的头节点。

代码

var detectCycle = function(head) { let map = new WeakMap(); let curr = head; while(curr) { if(!map.has(curr)) { map.set(curr, 1); } else { return curr; } curr = curr.next; } return null; }; 复杂度分析

时间复杂度：O(N)，其中 N 为数组长度。 空间复杂度：O(N)

[954545647]

用set记录访问

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

[dorian-byte]

思路：

这段代码是一个链表中检测环的问题，使用了快慢指针的方法。首先，将两个指针slow和fast都指向链表的头节点。然后，slow每次移动一个节点，fast每次移动两个节点，直到两个指针相遇或者到达链表末尾。

如果两个指针相遇，说明链表中存在环。此时，将fast重新指向链表头节点，并将slow保持在相遇位置。然后，将fast和slow同时每次移动一个节点，直到它们再次相遇，相遇的节点即为环的入口节点。

如果两个指针没有相遇，说明链表中不存在环，返回None。

代码：

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

复杂度分析：

时间复杂度：O(n)，其中 n 是链表的长度。快指针每次移动两个节点，慢指针每次移动一个节点，最多移动 n 次。

空间复杂度：O(1)，只使用了常数大小的额外空间。

(以上内容由ChatGPT生成。我通过对比ChatGPT的答案来修改自己写的代码，然后再自己打一遍。)

[YizheWill]

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

        slow, fast = head, head

        # First loop to find if cycle exists
        while (fast and fast.next):
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                break

        # If there's no cycle, return None
        if slow != fast:
            return None

        # Reset fast pointer to head
        # Both pointers now move at the same speed
        fast = head
        while fast != slow:
            fast = fast.next
            slow = slow.next

        return fast

[Moin-Jer]

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) {
                fast = head;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        return null;
    }
}