142.环形链表 II

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

• 142.环形链表 II

  • 题目描述

  • 方法 1：哈希法

    • 思路

    • 复杂度分析

    • 代码(JavaScript/C++)

  • 方法 2：双指针

    • 思路

    • 复杂度分析

    • 代码(JavaScript)

  • 方法 3：双指针 + 数学证明

    • 思路

    • 复杂度分析

    • 代码(JavaScript/C++)

题目描述

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

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

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

进阶：
你是否可以不用额外空间解决此题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/linked-list-cycle-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法 1：哈希法

思路

1. 可以从头开始遍历链表并给每个节点增加一个“已遍历”的标记；

2. 如果在遍历过程中遇到了一个“已遍历”的节点，说明这就是环的入口；

3. 但题目不允许修改给定的链表，所以我们可以用一个额外的 hashmap 来记录；

4. 注意题目中没有提到节点值是否唯一，所以仅用节点值作为 hashmap 的 key 是不够的，需要用到整个节点对象来当 key。

复杂度分析

• 时间复杂度：$O(n)$, n 为链表长度。

• 空间复杂度：$O(n)$。

代码(JavaScript/C++)

JavaScript Code

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function (head) {
  const map = new Map();

  while (head) {
    if (map.has(head)) return head;
    map.set(head, true);
    head = head.next;
  }

  return null;
};

C++ 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) {
        set<ListNode*> seen;
        ListNode *cur = head;
        while (cur != NULL) {
            if (seen.find(cur) != seen.end()) return cur;
            seen.insert(cur);
            cur = cur->next;
        }
        return NULL;
    }
};

方法 2：双指针

思路

1. 先使用快慢指针确定链表是否有环；

2. 如果链表有环，那快慢指针相遇的点一定是在环中；

3. 接着把指针 A 移到链表头部，指针 B 留在环内；

4. 指针 A 开始遍历环外的节点，指针 B 遍历环内的节点，指针 A 每走一步，指针 B 在环内走一圈；

5. 如果指针 A 和指针 B 相遇了，说明这个节点就是环的入口。

因为环和环外的唯一交点就是环的入口点

复杂度分析

• 时间复杂度：$O(n*p)$, n 是环外链表的长度，p 是环的长度。

• 空间复杂度：$O(1)$。

代码(JavaScript)

JavaScript Code

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @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) return findConnection(head, fast);
  }
  return null;

  // ******************************************

  function findConnection(head, loopNode) {
    // p1 走一步，p2 绕环一圈
    let p1 = head;
    while (true) {
      let p2 = loopNode;
      while (p2.next !== loopNode && p2.next !== p1) {
        p2 = p2.next;
      }
      if (p2.next === p1) return p1;
      p1 = p1.next;
    }
  }
};

Python Code

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

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        slow = fast = head

        while slow != None and fast != None and fast.next != None:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return self.findConnection(head, slow)
        return None

    def findConnection(self, head, loopNode):
        p1 = head
        while True:
            p2 = loopNode
            while p2.next != loopNode and p2.next != p1:
                p2 = p2.next
            if p2.next == p1:
                return p1
            p1 = p1.next

方法 3：双指针 + 数学证明

思路

先用快慢指针确定链表是否有环，如果是环形链表，快慢指针会在环内的某个节点相遇。

我们分别来看一下两个指针相遇前分别走了多少路程。

快指针

假设走到相遇点之前，快指针在环内走了 x 圈，那快指针走过的总路程可以用

S(fast) = a + x(b + c) + b

来表示，其中 (b + c) 就是环的长度。

慢指针

假设走到相遇点之前，慢指针在环内走了 y 圈，同理可得慢指针走过的总路程是

S(slow) = a + y(b + c) + b

而由于快指针的速度是慢指针速度的 2 倍，所以可得以下方程式：

2S(slow) = S(fast) => 2(a + x(b + c) + b) = a + y(b + c) + b

稍微整理一下我们就得到了：

a + b = (b + c)(x - 2y)

如果我们把其中一个指针移动到链表头部，然后让两个指针以相同的速度移动。

它们会在环的入口相遇。

复杂度分析

• 时间复杂度：$O(n)$，n 为链表长度。

• 空间复杂度：$O(1)$。

代码(JavaScript/C++)

JavaScript Code

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function (head) {
  let fast = head,
    slow = head;

  // 快慢指针确定有环
  while (fast && fast.next) {
    fast = fast.next.next;
    slow = slow.next;

    // 确定有环，开始找环的第一个节点
    if (fast === slow) {
      slow = head;
      while (slow !== fast) {
        slow = slow.next;
        fast = fast.next;
      }
      return slow;
    }
  }
  return null;
};

C++ 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) {
        ListNode *slow = head;
        ListNode *fast = head;

        while (fast && fast->next) {
            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;
    }
};

更多题解可以访问：https://github.com/suukii/91-days-algorithm