142. Linked List Cycle II

142. Linked List Cycle IIopen in new window

🟠 🔖 哈希表 链表 双指针 🔗 LeetCodeopen in new window

题目

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, returnnull.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to ( 0-indexed ). It is -1 if there is no cycle. Note thatpos is not passed as a parameter.

Do not modify the linked list.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

The number of the nodes in the list is in the range [0, 10^4].
-10^5 <= Node.val <= 10^5
pos is -1 or a valid index in the linked-list.

Follow up: Can you solve it using O(1) (i.e. constant) memory?

题目大意

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

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

解题思路

可以通过快慢指针的方法来解决。

定义两个指针，一个慢指针 slow，一个快指针 fast，初始位置都在链表的头部。
使用循环，每轮循环中慢指针走一步，快指针走两步。
如果链表中存在环，快指针最终会追上慢指针，两者会相遇。如果链表中不存在环，快指针会先到达链表的末尾。
如果相遇，将其中一个指针重新放置在链表头部，然后两个指针以相同的速度向前移动，每次移动一步。
当两个指针再次相遇时，相遇点即为环的入口点。

这个方法的原理证明如下：

假设链表头到环的入口点的距离为 a 步，环的入口点到相遇点的距离为 b 步，环的长度为 c 步。那么，在第一次相遇时，慢指针 slow 走了 a + b 步，快指针 fast 走了 a + b + k * c 步（其中 k 是快指针在环中转了 k 圈）。

由于快指针的速度是慢指针的两倍，所以：2(a + b) = a + b + k * c

整理得：a = (k - 1) * c + (c - b)

这意味着从相遇点继续走 a 步，将再次到达环的入口点。我们重新将 slow 指针放到链表头，然后 slow 和 fast 每次都移动一步，最终它们将在环的入口点相遇。

代码

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function (head) {
  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;
};

142. Linked List Cycle II

# 142. Linked List Cycle IIopen in new window

# 题目

# 题目大意

# 解题思路

# 代码

# 相关题目

142. Linked List Cycle IIopen in new window

题目

题目大意

解题思路

代码

相关题目