链表中环的入口节点

给定一个链表，返回链表开始入环的第一个节点。

从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回 null。

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

1.哈希表

思路：

  1. 利用哈希表建立一个标记数组 用于标记已经出现的next指针域
  2. while循环遍历链表 直到出现重复的next指针域 表示链表环开始出现
  3. 返回此时的链表结点指针 即为环入口结点

unordered_map

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    unordered_map<ListNode*, int> mark;
    ListNode *detectCycle(ListNode *head) {
        if (head == nullptr) return nullptr;
        ListNode* p = head;
        while (p) {
            if (mark[p]) return p;
            mark[p] = 1;
            p = p->next;
        }
        return nullptr;
    }
};

时间：12ms

内存：9.8mb

unordered_set

1
2
3
4
5
6
7
8
9
10
11
12
13
public:
    unordered_set<ListNode*> mark;
    ListNode *detectCycle(ListNode *head) {
        if (head == nullptr) return nullptr;
        ListNode* p = head;
        while (p) {
            if (mark.count(p)) return p;
            mark.insert(p);
            p = p->next;
        }
        return nullptr;
    }
};

时间：8ms

内存：9.3mb

复杂度

  • 时间复杂度：$O(N)$ 需要访问链表中的每一个结点
  • 空间复杂度：$O(N)$ 需要将链表中的结点保存在哈希表当中

2.双指针

相似问题：寻找距离尾部第k个结点、寻找环入口、寻找公共尾部入口

大致思路：

  1. 使用两个指针fast与slow从链表头部开始
  2. slow指针每次向后移动一个位置 fast指针每次向后移动两个位置
  3. 如果链表中存在环 则fast指针最终将会再次与slow指针相遇

详细步骤：

双指针第一次相遇：fast、slow指向链表头部head; fast每轮走2步、slow每轮走1步

  • case1:fast指针走过链表末端 说明链表中无环 直接返回nullptr
  • case2:当fast==slow时两指针在环中第一次相遇 分析fast与slow走过的步数关系
    • 设链表共有 a + b 个结点 其中链表头部到链表入口有a个结点 链表环中有b个结点，设两个指针分别走了f、s步则有：
    • fast走的步数为slow的两倍 f = 2s
    • fast比slow多走了n个环的长度 f = s + nb （n为整数）
    • 相减得到 f = 2nb s = nb（fast和slow指针分别走了 2n 和 n 个环的周长）

双指针第二次相遇：

  • slow指针位置不变 将fast指针重新指向链表头结点
  • slow 和 fast 同时每轮向前走1步
  • 当fast指针走到 f = a 步时 slow指针走到步 s = a + nb 此时两指针重合并同时指向环入口
  • 第2次相遇后返回slow指针指向的结点即可

encounter1

image-20230714123936513

image-20230714123952602

encounter2

image-20230714124118350

image-20230714124128656

reference

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head, *slow = head;
        //1.construct the first encounter
        while (true) {
            if (fast == nullptr || fast->next == nullptr) return nullptr;
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) break;
        }
        //2.construct the second encounter
        fast = head;
        while (fast != slow) {
            slow = slow->next;
            fast = fast->next;
        }
        return fast;
    }
};

时间：4ms

内存：7.4mb

复杂度

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