环形链表

环形链表 I

给你一个链表的头节点 head ,判断链表中是否有环

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

示例

解析 思路

代码解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/

bool hasCycle(struct ListNode *head)
{
struct ListNode *fast = head, *slow = head;
while(fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if(fast == slow)
{
return true;
}
}
return false;
}

延伸问题

问题一

为什么slow和fast一定会相遇? (fast走两步 slow走一步) 会不会在环里错过 永远追不上? 请证明!

分析证明

  • 设 起点到入环前距离 为 L , 整环长 C ,
  1. slow和fast, fast 走 L 到入环口,slow走了 L/2
  2. slow走 L , 此时fast已经走了 2L (跟C的大小有关系)

假设slow走 L 进环的时候, slow和fast距离为 N

  • fast开始追slow slow走一步 fast走两步 每走一步判断一次是否相遇
  • 每追一次 fast和slow的距离变化 N,N-1,N-2,N-3,----,1,0
  • 当距离为 0 两者相遇

假设slow一次一步 fast一次三步 slow进环后 两者距离N fast追slow
距离变化:

  • 当N为偶数: N, N-2, N-4 ,N-6, …, 2 ,0 —> 可以追上
  • 当N为奇数: N, N-2, N-4 ,N-6, …, 1, -1 —> 此次追不上
    • 距离变成-1 说明 他们之间的距离变成了 C-1
      • 如果 C-1 为奇数 : 永远追不上
      • 如果 C-1 为偶数 : 可以追上

问题二

为什么slow走一步,fast走两步呢? 能不能fast一次走n步呢?(n>2) 请证明!

n步的推导过程与上面相似

假设slow一次一步 fast一次四步 slow进环后 两者距离N fast追slow
距离变化:

  • 当N为3的倍数: N, N-3, N-9, N-9, …, 3, 0 —> 可以追上
  • N不为3的倍数: N, N-3, N-9, N-9, …, 2, -1 —> 此次追不上
    • 意味着距离为 C-1
  • N不为3的倍数: N, N-3, N-9, N-9, …, 1, -2 —> 此次追不上
    • 意味着距离为 C-2
  • 如果 C-1C-2 为3的倍数 : 可以追上 不是则永远无法相遇

fast走n步 n再继续变大 以此类推

结论

问题一 --> 一定会相遇
问题二 --> fast一次走n步, 如果n>2 不一定会相遇

环形链表 II

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

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

已经证明slow走一步fast走两步 一定会相遇 如何求入口点呢 证明?

结论 : 一个指针从相遇点开始走 一个指针从链表头开始走 他们会在环入口相遇

方法一 数学推导

思想不好理解 实现简单
数学方法推导

代码实现

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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *detectCycle(struct ListNode *head)
{
struct ListNode *slow = head,*fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast) // 如果相遇
{
struct ListNode *meet = slow; // 定义meetnode
while(meet != head) // 公式证明
{

meet = meet->next;
head = head->next;
}
return meet;
}

}
return NULL;
}

方法二 直接法

思想简单 实现复杂一点点

看清题目要求 : 不能改变链表
代码实现

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
struct ListNode *tailA = headA;
struct ListNode *tailB = headB;
int lenA, lenB;
lenA = lenB = 1;
while(tailA->next)
{
lenA++;
tailA = tailA->next;
}
while(tailB->next)
{
lenB++;
tailB = tailB->next;
}
// 判断尾节点是否相同
if(tailA != tailB)
{
return NULL;
}
// 求差步
int gap = abs(lenB-lenA);
struct ListNode* longlist = headA;
struct ListNode* shortlist = headB;
if (lenA<lenB)
{
longlist = headB;
shortlist = headA;
}
// 熟练使用这种迭代!!! 别老是用for
while(gap--)
{
longlist = longlist->next;
}
while(longlist != shortlist)
{
longlist = longlist->next;
shortlist = shortlist->next;
}
return longlist;

}

struct ListNode *detectCycle(struct ListNode *head)
{
struct ListNode *slow = head,*fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast) // 如果相遇
{
struct ListNode * meet = slow; // 定义meetnode
struct ListNode * newlist = meet->next;
struct ListNode * record = newlist;
meet->next = NULL;
struct ListNode * cur = head;
struct ListNode * node = getIntersectionNode(cur, newlist);
slow->next = newlist;
return node;
}

}
return NULL;
}

meet为相遇点 由此处断开 转换成两个链表相交 题目又要求不可改变链表结构 所以需要记录newlist的值 最后接回来