142.环形链表 II

发表于 | 分类于
字数统计: 423 | 阅读时长 ≈ 1

一、题目描述

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

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

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

示例 1：

1
2
3
输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。

circularlinkedlist.png

示例 2：

1
2
3
输入：head = [1,2], pos = 0
输出：tail connects to node index 0
解释：链表中有一个环，其尾部连接到第一个节点。

circularlinkedlist_test2.png

示例 3：

1
2
3
输入：head = [1], pos = -1
输出：no cycle
解释：链表中没有环。

circularlinkedlist_test3.png

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

二、题解

1.算法描述

  • 双指针

2.个人分析

  1. 使用快慢双指针确认链表是否有环

  2. 如果有环，找到入环节点。

    我有一点搞不太明白的就是，如果有环，那么最终慢指针停下的位置与入环节点的距离==头节点与入环节点的距离。利用这一性质，可以找到入环节点。

3.代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head)
{
    if (!head || !head->next)
        return NULL;
    struct ListNode *fast = head, *slow = head;
    int hasCycle = 0;
    while (fast->next != NULL && fast->next->next != NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
        {
            hasCycle = 1;
            break;
        }
    }
    if (hasCycle)
    {
        while (head != slow)
        {
            head = head->next;
            slow = slow->next;
        }
        return head;
    }
    return NULL;
}