【环形链表】

前言

大家好，我是熊猫，今天我们来讲解几道有趣的链表题，希望大家可以在不断的打怪升级中提升自己的核心战斗力！

---

一、相交链表

160. 相交链表

给你两个单链表的头节点 headA 和 headB ，
请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
> 题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。

（一）题目分析

我们先来看一下题目：
题目给了两个链表，这两个链表可能有相交部分，也可能没有，
如果有：就返回相交的第一个节点，
如果没有：就返回NULL.
需要注意的一点是：我们不能改变原链表。

1、最简单的方法：暴力破解 我们直接给它套上两层循环、依次遍历每个节点，
当两个节点都遍历到空时则表明没有相交节点，否则第一个想等的节点就是第一个相交的节点（相等指的是地址相等而非数值相等）。

不过显而易见，这种方法的时间复杂度为O(n^2)，空间复杂度为O(1)

2.那么我们能否将该算法化简，将时间复杂度降低呢？
这里我们可以先分别计算出两个链表的长度，计算它们的差值dif，
让长的链表先走dif步，之后两个链表就可以一起往前走，当两个节点相同时，我们就找到了第一个相交的节点，
当然，如果没有相交节点，两个链表最后都会指向空的。
动画演示：

（二）题目代码

代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode LN;

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
	int lenA = 0;
	int lenB = 0;
	LN* curA = headA;
	LN* curB = headB;
	// 说明1：下面的代码中我们两个链表都少走了一步，这是为了找到最后一个节点，
	// 如果最后一个节点都不相等，那就表明没有相交节点，我们就不要继续后面的比较操作了
	// 说明2：两个链表都少走一步，对差值无影响
	while (curA->next) // 最后都指向最后一个节点
	{
		lenA++;
		curA = curA->next;
	}
	while (curB->next)
	{
		lenB++;
		curB = curB->next;
	}

	if (curA != curB) // 如果最后一个节点地址不同，说明没有相交节点
		return NULL;

	int dif = abs(lenA - lenB); // 计算差值
	LN* longHead = headA;
	LN* shotHead = headB;
	if (lenA < lenB) // 找到长短链表
	{
		longHead = headB;
		shotHead = headA;
	}

	while (dif--) // 长链表先走差值步
	{
		longHead = longHead->next;
	}

	while (longHead != shotHead) // 之后一起走
	{
		longHead = longHead->next;
		shotHead = shotHead->next;
	}

	return longHead;
}

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

提交实例：

---

二、环形链表 ①

141. 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。

（一）题目分析

题目给了我们一个链表让我们判断链表中是否存在环，那么我们是否可以直接遍历一遍呢？
没有环就会遍历到NULL，那我们就可以直接返回FALSE，否则如果存在环的话就会走到重复的节点，那就返回TRUE不就好啦？
一开始肯定会有同学会这样想，但是实际上，如果不存在环的话我们很容易判断，可如果有环的话我们又怎么判断这个节点是已经走过的节点呢？我们只会在环中无限循序直至超出时间限制。

我们需要换一种解题方式，这里我们只用一个指针时肯定无法判断一个节点是否已经走过的，那么我们是否可以再增加一个指针，两个指针走的速度不同，走的快的指针先入环，走的慢的指针后入环，
之后这个题目就变成了追及与相遇问题，两个指针都在环中走，走的快的肯定可以追上走的慢的，当它们相遇时就说明存在环，否则当走的快的遇到NULL时，就说明不存在环。

循环链表--1

循环链表--2

（二）题目代码

示例：

typedef struct ListNode LN;

bool hasCycle(LN* head) {
	if (!head)
		return false;

	LN* fast = head;
	LN* slow = head;
	while (fast && fast->next)
	{
		fast = fast->next->next;
		slow = slow->next;

		if (fast == slow)
			return true;
	}

	return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

提交实例：

上面我们写的fast速度为slow速度的两倍，其实也可以写成三倍，四倍，五倍等等，只要一个跑的快，一个跑的慢最后就都会相遇，不过跑过的圈数会有所不同。

---

三、环形链表 ②

142. 环形链表 II

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

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

不允许修改 链表。

（一）解法1 – 数学分析，公式推导

题目分析

在上一题我们能够确定一个链表中是否带有环，同时我们也看了相关的两个视频，
下面我们来分析一下两者的运动路程：

题目代码

示例：

typedef struct ListNode LN;

LN* hasCycle(LN* head) {

	LN* fast = head;
	LN* slow = head;
	while (fast && fast->next)
	{
		fast = fast->next->next;
		slow = slow->next;

		if (fast == slow)
			return fast;
	}
	return NULL;
}

LN* detectCycle(LN* head)
{
	if (!head)
		return head;

	LN* meet = hasCycle(head);
	if (!meet)  //没有环
		return meet;

    LN* cur =head;
	while (meet != cur)
	{
		meet = meet->next;
		cur = cur->next;
	}

	return meet;
}
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

提交实例：

---

（二）解法2 – 切断环，改变问题为相交链表

题目分析

在第二题中我们可以判断一个链表有没有带环，在第一题中我们可以找到一个两个相交链表的第一个相交节点，
说到这里我想大家已经知道我们下一步应该怎么做了吧！
我们在判断链表存在环之后可以将环从相遇点断开（新链表从相遇点开始），我们直接找相交链表的第一个相交节点即可。

视频解析：

切断循环链表

题目代码

示例：

typedef struct ListNode LN;

 LN* hasCycle(LN* head) {

 	LN* fast = head;
 	LN* slow = head;
 	while (fast && fast->next)
 	{
 		fast = fast->next->next;
 		slow = slow->next;

 		if (fast == slow)
 			return fast;
 	}
     return NULL;
 }

 LN* getIntersectionNode(LN* headA, LN* headB) {
 	int lenA = 0;
 	int lenB = 0;
 	LN* curA = headA;
 	LN* curB = headB;
 	while (curA) // 获取长度
 	{
 		lenA++;
 		curA = curA->next;
 	}
 	while (curB)
 	{
 		lenB++;
 		curB = curB->next;
 	}

 	int dif = abs(lenA - lenB); // 计算差值
 	LN* longHead = headA;
 	LN* shotHead = headB;
 	if (lenA < lenB) // 找到长短链表
 	{
 		longHead = headB;
 		shotHead = headA;
 	}

 	while (dif--) // 长链表先走差值步
 	{
 		longHead = longHead->next;
 	}

 	while (longHead != shotHead) // 之后一起走
 	{
 		longHead = longHead->next;
 		shotHead = shotHead->next;
 	}

 	return longHead;
 }

 LN* detectCycle(LN* head) {
 	if (!head)
 		return head;
 	LN* meet = hasCycle(head); // 找到一个相遇点
 	if (!meet) // 没有环就退出
 		return NULL;
 	LN* next = meet->next;
 	meet->next = NULL; //  断开环
 	meet = next; // 此时问题变成了寻找两个链表相交的问题
 	return getIntersectionNode(meet, head);

 }
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

提交实例：

---

（三）解法3 – 改变链表，使得每个节点自环

题目分析

这里我们提供一种“错误的方法”：
遍历链表，每次都使相应的节点的next指针指向自己（自环），如果链表不带环就会走到NULL，如果链表本身就是带环的话我们就能够回到我们设置的自环节点，并且该节点就是入环的第一个节点。
（这里之所以说是错误的方法并不是说得不到正确的结果，只是这种方法对链表改动过大，无法通过LeetCode的检测）
视频解析：

题目代码

示例：

typedef struct ListNode LN;

LN* detectCycle(LN* head) {
 	if (!head)
 		return head;

 	LN* cur = head;
 	while (cur)
 	{
 		LN* next = cur->next;
 		if (cur == next)
 			return cur;
 		cur->next = cur;
 		cur = next;
 	}

 	return NULL;
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

运行实例：

---

总结

以上就是今天讲解的环形链表的全部内容，如果大家有什么疑问或者建议都可以在评论区留言，感谢大家对的支持。