跟着灵茶山艾府大佬学习算法思路的day5，目标是在一个月内掌握hot100
b站链接如下：
链表的中间节点 题目描述：
给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例 1：
1
2
3
输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。
示例 2：
1
2
3
输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。
思路：
快慢指针梦开始的地方，根据图示可知，当快指针指向空，或者下一个节点指向空就退出循环。
代码：
1
2
3
4
5
6
7
8
9
var middleNode = function(head) {
slow = head;
fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
};
总结：
是其他需要找中点的题目的基础。
环形链表 题目描述：
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
1
2
3
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
1
2
3
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
1
2
3
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
思路：
如果有环，慢指针会走入环中，而快指针就有机会追上慢指针。那么只要快指针能与慢指针指向同一个节点，就说明有环；否则快指针正常来到末尾，说明无环。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var hasCycle = function(head) {
if (!head || !head.next) return false; // 这个判断可以删去，即使只有一个节点或无节点，下面的循环一样可以处理
let slow = head;
let fast = head;
// 快指针每次走两步，需要确保fast和fast.next都不为空
while (fast && fast.next) {
slow = slow.next; // 慢指针走一步
fast = fast.next.next; // 快指针走两步
if (slow === fast) { // 如果相遇，说明有环
return true;
}
}
return false; // 快指针到达末尾，说明无环
};
总结：
感觉没有太多可说的，放一下灵神的答疑。
环形链表 II 题目描述：
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
1
2
3
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
1
2
3
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
1
2
3
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
思路：
这题新增了一个要求，不仅要判断有环，还要找到环的入口，环的入口的寻找就要涉及一些数学推论了。
可设头结点到入口的距离为a，入口到相遇点的距离为b，相遇口到入口的距离为c。可以知道快慢相遇时，慢指针是一定没有走完一圈的，快指针会将慢指针套圈。
这里slow和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
var detectCycle = function(head) {
let slow = head;
let fast = head;
// 第一阶段：判断是否有环，找到相遇点
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) { // 有环
// 第二阶段：找环的入口
let ptr1 = head; // 从链表头开始
let ptr2 = slow; // 从相遇点开始
while (ptr1 !== ptr2) {
ptr1 = ptr1.next;
ptr2 = ptr2.next;
}
return ptr1; // 环的入口
}
}
return null; // 无环
};
总结：
这题相较于上一题判断是否有环，新增了一个循环来找到入口，这个入口的寻找与一个简单的数学推论有关，动笔算一算就比较容易理解了。关键在于要知道在相遇时，快指针有可能已走n圈。
重排链表 题目描述：
给定一个单链表 L 的头节点 head ，单链表 L 表示为：
1
L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：
1
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1：
1
2
输入：head = [1,2,3,4]
输出：[1,4,2,3]
示例 2：
1
2
输入：head = [1,2,3,4,5]
输出：[1,5,2,4,3]
思路：
这个重排过程可以理解成两步。第一步是先找到中间节点，反转中间节点后面的链表，得到如下两段链表：
值得注意的是，此时值为3的节点是指向空节点的，因为一开始pre为null，这点是需要注意的。在代码逻辑中也会借助这点来结束重排的循环。
然后逐个处理head和head2，推进这两个指针的同时将head2插入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
var reorderList = function(head) {
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
} // slow 此时指向中点
let pre = null;
let cur = slow;
while ( cur !== null) {
let next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
} // pre 此时指向原链表最后一个节点，也即反转链表的第一个节点
let head2 = pre;
while (head2.next !== null) {
const nxt = head.next;
const nxt2 = head2.next;
head.next = head2;
head2.next = nxt;
head = nxt;
head2 = nxt2;
}
};
思路：
最难的地方在于如何拆解重排逻辑，找到中点后反转再插入以实现的思路并不是那么好想的。