142.环形链表 II

一、题目描述

给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 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;
}