# 纲要
> 主干纲要、Hint/线索/路标
- **链表节点操作**
- **获取节点**：
- 获取链表中**第 k 个节点**
- 获取链表**倒数第 k 个节点**
- 获取链表**中间节点** ⭐
- 获取链表**尾节点**
- **删除节点**：
- 删除**第 k 个节点**
- 删除**倒数第 k 个节点**
- 删除**中间节点** ⭐
- 删除**给定节点**（非尾节点） ⭐
- 删除指定值的所有节点
- 删除**有序**链表中的**重复节点**（重复值保留一个，或者全删）
- **交换节点**：
- 两两交换链表中的节点
- **链表整体操作**
- **反转链表**
- 反转整个链表；
- 反转链表指定区段 `[left, right]`
- k 个一组反转链表；
- **旋转链表**
- **链表拆分**
- **拆出头部长度为 L 的一段**
- **均等拆分**（拆为前后近似均等的两段）
- **奇偶节点拆分**
- **按值拆分**
- **链表合并**：
- **插空合并两个链表**
- 合并两个升序链表
- 合并 k 个升序链表
- **链表排序**
- 插入排序
- 归并排序
- 链表专题问题
- **环形链表**：判断链表是否有环，求环的入口节点，求环长等；
- **相交链表**：判断两链表是否相交
- **判断回文链表**
- 链表模拟
- **模拟两数相加**（逆序 / 正序表示两个数）
%%
# Q&A
#### 已明确
#### 待明确
> 当下仍存有的疑惑
**❓<font color="#c0504d"> 有什么问题？</font>**
# Buffer
## 闪念
> sudden idea
## 候选资料
> Read it later
%%
<br><br>
# 链表节点操作
## 获取节点
##### 获取链表中第 k 个节点
```cpp
// 获取链表中的第k个节点, 不存在时返回null;
ListNode* GetKthNode(ListNode * head, int k) {
if (!head || k <= 0) return nullptr;
int step = k - 1;
while (head && step--) { // 节点数量足够时, 最后step会减为-1而非0.
head = head->next;
}
return head; // head可能为空
}
```
##### 获取链表中倒数第 k 个节点
- `ahead` 指针从 `head` 开始**先走 k 步后**，再让 `cur` 指针从`head` 开始，二者同步走；
- 两指针每次走一步，当 `ahead` 指向 `nullptr` 时，`cur` 恰好指向倒数第 k 个节点。
```cpp
// 获取链表中的倒数第k个节点
ListNode* GetKthNodeFromEnd(ListNode *head, int k){
if (!head || k <= 0) return nullptr;
ListNode *cur = head, *ahead = head;
while (ahead && k--) { // ahead比cur先走k步, 再同步走; 当ahead走向nullptr时, cur正好指向倒数第k个节点;
ahead = ahead->next;
}
// 注意这里k可能为-1, 不能用if(k)判断!
if (k > 0) return nullptr; // ahead没走完k步, 即链表长度小于k, 不存在倒数第k个节点.
while (ahead) {
cur = cur->next;
ahead = ahead->next;
}
return cur;
}
```
##### 获取链表中间节点
**应用快慢指针**：
![[Excalidraw-Solution/链表_1.excalidraw.svg|729]]
%%[[Excalidraw-Solution/链表_1.excalidraw.md|🖋 Edit in Excalidraw]]%%
```cpp
ListNode* GetMiddleNode(ListNode *head) {
if (!head || !head->next) return head;
ListNode *slow = head, *fast = head->next;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
}
return slow; // 链表偶数长时, slow指向前半段尾节点, fast恰指向尾节点.
// 如果希望链表偶数长时, slow指向后半段首节点, 则再移动一步.
// if (fast) {
// slow = slow->next;
// }
// return slow;
}
```
##### 获取链表尾节点
```cpp
ListNode * GetTailNode(ListNode * head) {
while (head && head->next) {
head = head->next;
}
return head;
}
```
<br>
## 删除节点
##### 删除第 k 个节点
```cpp
ListNode* DeleteKthNode(ListNode *head, int k) {
if (!head || k <= 0) return head; // 无操作
ListNode dummy(0, head), *prev = &dummy;
int step = k - 1; // 删除第k个节点, p从dummy出发, 走k-1步, 指向第k-1个节点
while (prev && step--) {
prev = prev->next;
}
if (prev && prev->next) { // 第k-1个节点, 第k个节点均存在
ListNode *del = prev->next;
prev->next = prev->next->next;
delete del;
}
return dummy.next;
}
```
##### 删除倒数第 k 个节点
```cpp
// 删除链表中的倒数第k个节点
ListNode* DeleteKthNodeFromEnd(ListNode *head, int k){
if (!head || k <= 0) return head;
ListNode dummy(0, head);
ListNode *prev = &dummy, *ahead = head;
while (ahead && k--) { // ahead从head起先走k步, prevDel再从dummy出发, 与ahead同步走.
ahead = ahead->next;
}
if (k > 0) return dummy.next; // 若k未能减到小于0(上面循环结束后k==-1), 意味着链表长度小于k, 不存在倒数第k个节点
while (ahead) {
ahead = ahead->next;
prev = prev->next;
}
ListNode *del = prev->next;
prev->next = prev->next->next; // 链表长度大于等于k, 倒数第k个节点必然存在
delete del;
return dummy.next;
}
```
##### 删除中间节点
沿用"**快慢指针**"获取**链表中点**的思路:
- 若链表长度为偶数，当 `fast` 指向尾节点时，**`slow` 恰好指向前半段尾节点, 即为需删除的后半段首节点的前驱节点**;
- 若链表长度为奇数，当 `fast` 指向空时，**`slow` 恰好指向待删除的链表中间节点**。
- => **要使 slow 少走一步而指向前驱节点**, 故 **`fast` 需要在停留在倒数第二个节点**，
因此循环条件改为 `fast->next && fast->next->next`，仅当 `fast` **后两个节点均存在时才后移**。
> [!summary]
>
> - 定位 "**中点**" 时，是**快慢指针==分别从 `head` , `head->next` 出发==**， `while(fast && fast->next)` 时移动；
> - 定位 "**中点的前驱顶点**"，则**快慢指针==同时从 `dummy` 出发==**，`while (fast && fast->next && fast->next->next)` 时移动。
>
```cpp
// 删除链表中间节点 (特指"下标为n/2下取整"的节点, 即偶数长时, 后半段的首节点)
ListNode* DeleteMiddleNode(ListNode *head) {
if (!head) return nullptr; //
if (!head->next) {
delete head;
return nullptr;
}
ListNode *slow = head, *fast = head->next;
while (fast && fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
ListNode *del = slow->next;
slow->next = slow->next->next;
delete del;
return head; // 当链表长度>=2时, 删除的必然不是头结点, 故head必然存在.
}
```
##### 删除给定链表节点 （非尾节点）
```cpp
// 删除链表中某个给定节点(非尾节点), 头节点未知 => 替换该节点与后一节点的值, 然后删掉后一节点.
void DeleteTargetNode(ListNode *node) {
if (node && node->next) {
node->val = node->next->val;
ListNode *tmp = node->next;
node->next = node->next->next;
delete tmp;
}
}
```
##### 删除指定值的所有节点
```cpp
// 删除链表中值为给定值的所有节点
ListNode* RemoveValueFromList(ListNode *head, int val) {
if (!head) return nullptr;
ListNode dummy(0, head), *prev = &dummy;
while (prev->next) {
if (prev->next->val == val) {
ListNode *tmp = prev->next;
prev->next = prev->next->next;
delete tmp;
} else {
prev = prev->next;
}
}
return dummy.next;
}
```
##### 删除有序链表中的重复节点
- 对于存在重复值的节点，**保留其中一个**
```cpp
// 删除"有序"链表中的多余重复节点, 使得每个值只保留一次
ListNode* RemoveDuplicateNode(ListNode *head) {
if (!head || !head->next) return head;
ListNode *p = head;
while (p->next) {
if (p->next->val == p->val) {
ListNode *tmp = p->next;
p->next = p->next->next;
delete tmp;
} else {
p = p->next;
}
}
return head;
}
```
- 对于存在重复值的节点，**全部删除**
```cpp
// 删除"有序"链表中的所有重复节点. 即出现1次以上的值, 全部删除, 一个也不保留
ListNode* RemoveAllDuplicateNode(ListNode *head) {
if (!head || !head->next) return head;
ListNode dummy(-1, head), *prev = &dummy;
while (prev->next && prev->next->next) {
if (prev->next->val == prev->next->next->val) {
int x = prev->next->val;
while (prev->next && prev->next->val == x) {
ListNode *tmp = prev->next;
prev->next = prev->next->next;
delete tmp;
}
} else {
prev = prev->next;
}
}
return dummy.next;
}
```
<br>
## 交换节点
##### 两两一组交换组内的相邻两节点
```cpp
// 迭代的写法
ListNode *SwapPairs(ListNode *head) {
if (!head || !head->next) return head;
ListNode dummy(-1, head), *prev = &dummy;
while (prev->next && prev->next->next) {
ListNode *p1 = prev->next, *p2 = prev->next->next;
p1->next = p2->next;
p2->next = p1;
prev->next = p2;
prev = p1;
}
return dummy.next;
}
// 递归的写法
ListNode *SwapPairsRecur(ListNode *head) {
if (!head || !head->next) return head;
ListNode *p1 = head, *p2 = head->next;
p1->next = SwapPairsRecur(p2->next);
p2->next = p1;
return p2;
}
```
<br><br><br>
# 链表操作
## 反转链表
##### 反转整个链表
```cpp
// 思路一: 三指针原地反转
ListNode* ReverseList(ListNode *head) {
ListNode *prev = nullptr, *cur = head;
while (cur) {
ListNode *nxt = cur->next;
cur->next = prev;
prev = cur;
cur = nxt;
}
return prev;
}
// 思路二: 头插法反转
ListNode* ReverseListByInsertToHead(ListNode *head) {
if (!head) return nullptr;
ListNode dummy(-1, head);
while (head->next) {
ListNode *p = head->next;
head->next = head->next->next;
p->next = dummy.next;
dummy.next = p;
}
return dummy.next;
}
// 思路二: 头插法反转, 写法二
ListNode* ReverseListByInsertToHead(ListNode *head) {
if (!head) return nullptr;
ListNode dummy(-1, nullptr);
while (head) {
ListNode *p = head;
head = head->next;
p->next = dummy.next;
dummy.next = p;
}
return dummy.next;
}
// 思路三: 递归
ListNode* reverseListReCur(ListNode* head) {
if (!head || !head->next) return head;
ListNode* rest = head->next; // 暂存head->next, 同时对head->next起始的部分进行反转.
ListNode* new_head = reverseListRecur(rest);
rest->next = head;
head->next = nullptr;
return new_head;
}
```
##### 反转部分链表
```cpp
// 反转[left, right]区间的链表. 节点下标从1开始, 若left或right越界则返回, 不操作)
// 头插法反转
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode dummy(0, head), *prev = &dummy;
int step = left - 1;
while (prev && step--) { // 从dummy起走left-1步, prev_l指向l的前驱节点.
prev = prev->next;
}
if (!prev || !prev->next) return head;
// 头插法: 每次将l->next插入到prev->next;
ListNode* l = prev->next;
for (int i = 0; l->next && i < right - left; ++i) { // 初始时l=prev->next, 共需要对prev->next右侧的right-left个节点进行头插反转.
auto node = l->next;
l->next = node->next;
node->next = prev->next;
prev->next = node;
}
return dummy.next;
}
```
##### K 个一组反转链表
```cpp
ListNode* reverseKGroup(ListNode* head, int k) {
if (!head || k <= 0) return head;
ListNode dummy(0, nullptr), *prev = &dummy;
while (head) { // head指向剩余待处理链表头部.
ListNode* ahead = head; // ahead从head出发, 走k步, 确保存在k个节点.
int step = k;
while (ahead && step--) {
ahead = ahead->next;
}
if (step > 0) { // 若剩余链表不足k个节点, 不进行处理, 直接将head接给prev->next.
prev->next = head;
break;
}
ListNode *tail = head; // tail指向剩余链表头结点, 将k个节点反转后即位于该组尾部.
while (head != ahead) { // 当存在至少k个节点时, ahead位于这k个节点之后.
ListNode *cur = head;
head = head->next;
cur->next = prev->next;
prev->next = cur;
}
prev = tail;
}
return dummy.next;
}
```
<br>
## 旋转链表
1. 首尾连成环；
2. 右移 k 位，则需要找到**原链表中倒数第 k 个节点的前驱节点**，在其后断开，以其后的**倒数第 k 个节点为新的头结点**。
```cpp
/* 链表右移k位
* 每个节点右移k位, 即原链表中最后k个节点移动到前面, 倒数第k个节点变成头节点.
* 因此处理步骤是:
* 1. 将链表首尾相连, 得到环, 以及链表总长L;
* 2. 从原始的头节点开始, 移动L-k-1步, 指向原链表中的第L-k个节点, 其后一节点即为倒数第k个节点.
* 3. 断开第L-K个节点与倒数第K个节点之间的连边, 以后者为头节点返回, 即得到旋转后的新链表
* 4. 如果k值为负, 则整个链表将会向左旋转.
*/
ListNode* RotateRightList(ListNode* head, int k) {
if (!head || !head->next) return head;
ListNode *tail = head;
int length = 1;
while (tail->next) { // 获取尾节点和链表长
++length;
tail = tail->next;
}
k %= length;
if (k == 0) return head;
tail->next = head; // 首尾相连
int step = length - k - 1; // prev从head起走n-k-1步, 即指向倒数第k个节点的前驱节点.
ListNode *prev = head;
while (prev && step--) {
prev = prev->next;
}
head = prev->next;
prev->next = nullptr;
return head;
}
```
<br>
## 合并链表
##### 插空合并两条链表
要求：**将 `l2` 插空合并到 `l1` 之中**。若 `l2` 较长，则插空完成后，剩余部分直接接到 `l1` 尾部。
- 思路一：当 `l1` 与 `l2` 均存在时，**每次取出两链表头部节点 `p1` 和 `p2`** ，并将 `l1` 与 `l2` 后移。
- 令 `p1` 指向 `p2`，此时再判断 `p2` 的指向：若 `l1` 还有剩余则指向 `l1`，否则指向 `p2`；
- 思路二：令 `prev` 在`l1` 链表节点上移动，每次从 `l2` 中取出一个节点，插入到 `prev` 之后。
- 最后若 `l2` 还有剩余，则将剩余的 `l2` 链表整个接在`prev` 之后。
```cpp
// 插空合并两个链表 (将l2插空合并到l1之中, 若l2较长, 则插空完成后,剩余部分直接接到l1尾部)
// 实现一: 初始时用head指向l1. 每次取出l1和l2头部的节点p1和p2, 将p1指向p2, p2再指向剩余的l1(如果存在)或l2.
ListNode* MergeTwoListNodeCutIn(ListNode *l1, ListNode *l2) {
if (!l1) return l2;
if (!l2) return l1;
ListNode *head = l1;
while (l1 && l2) {
ListNode *p1 = l1, *p2 = l2; // 取出l1和l2头部的两个节点p1, p2;
l1 = l1->next;
l2 = l2->next;
p1->next = p2;
p2->next = (l1 ? l1 : l2); // 如果l1为空, 则p2指向剩余的l2
}
return head;
}
// 插空合并两个链表 (将l2插空合并到l1之中, 若l2较长, 则插空完成后,剩余部分直接接到l1尾部)
// 实现二: p1在原l1的节点上移动, 如果l2中还存在节点, 就将其插入p1之后
ListNode* MergeTwoListNodeCutIn2(ListNode *l1, ListNode *l2) {
if (!l1) return l2;
if (!l2) return l1;
ListNode *prev = l1; // prev原l1的节点上移动. 如果l2中还存在节点, 就将其插入prev之后.
while (prev->next && l2) { // 注意, 避免prev指向空, 因为最后可能要插入剩余的l2
ListNode *p = l2;
l2 = l2->next;
p->next = prev->next;
prev->next = p;
prev = prev->next->next; // prev跳过刚插入其后的p2节点.
}
if (l2) { // 如果l1还有剩余, 无需处理; 如果l2还有剩余, 直接追加到p1之后
prev->next = l2;
}
return l1;
}
```
##### 合并两条有序链表
```cpp
ListNode * MergeTwoSortedList(ListNode *l1, ListNode *l2) {
if (l1) return l2;
if (l2) return l1;
ListNode dummy(0, nullptr), *prev = &dummy;
while (l1 && l2) {
if (l1->val <= l2->val) {
prev->next = l1;
l1 = l1->next;
} else {
prev->next = l2;
l2 = l2->next;
}
prev = prev->next;
}
prev->next = l1 ? l1 : l2;
return dummy.next;
}
```
##### 合并 k 条升序链表
> 参见 [[99-题解/leetcode/lc-23 合并 K 个升序链表|lc-23 合并 K 个升序链表]]，可采用 "堆" 的方式。
<br>
<br>
## 拆分链表
#### 均等拆分
偶数长度时，拆分为**等长两段**；奇数长度时，拆分为**前一段比后一段长 1 的两段**。
```cpp
// 使用快慢指针确定链表中点, 由此进行拆分.
pair<ListNode*, ListNode*> splitList(ListNode* head) {
if (!head || !head->next) return { head, nullptr };
ListNode *slow = head, *fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
ListNode *new_head = slow->next;
slow->next = nullptr;
return { head, new_head } ;
}
```
##### 拆出头部指定长度的链表
```cpp
// 拆分出头部一段长度为n的链表, 返回剩余链表的头节点.
ListNode* curFront(ListNode* head, int n) {
if (n <= 0) return head;
int step = n - 1;
while (head && step--) {
head = head->next;
}
if (head) {
ListNode* rest = head->next;
head->next = nullptr;
return rest;
}
return nullptr;
}
```
##### 按奇偶节点拆分成两条链表
```cpp
// 拆分链表: 按奇偶拆分, 返回偶数节点拆分得到的链表
// 拆分链表: 按奇偶拆分, 返回偶数节点拆分得到的链表
ListNode* PartitionEven(ListNode* head) {
if (!head || !head->next) return nullptr;
ListNode dummy(0, nullptr), *prev = &dummy;
while (head && head->next) { // 每次处理两个节点, 将其中第二个追加到prev->next.
prev->next = head->next;
prev = prev->next;
head->next = head->next->next;
head = head->next;
}
prev->next = nullptr; // 记得置空! 其后可能还连有节点.
return dummy.next;
}
```
##### 按值拆分
小于 `x` 的为一段，大于等于 `x` 的为另一段。
> [!caution] 注意最后将两条链表尾置空！
```cpp
pair<ListNode*, ListNode*> splitListByValue(ListNode* head, int x) {
ListNode dummy1(0, nullptr), dummy2(0, nullptr);
ListNode *prev1 = &dummy1, *prev2 = &dummy2;
while (head) {
if (head->val < x) {
prev1->next = head;
prev1 = prev1->next;
} else {
prev2->next = head;
prev2 = prev2->next;
}
head = head->next;
}
prev1->next = nullptr; // 注意将链表尾置空!!确保断开.
prev2->next = nullptr;
return { dummy1.next, dummy1.next };
}
```
<br><br>
## 排序链表
> 参见 [[99-题解/leetcode/lc-148 排序链表|lc-148 排序链表]]
##### 插入排序
```cpp
ListNode* sortList(ListNode* head) {
if (!head || !head->next) return head;
ListNode dummy(0, head), *prev = head;
while (prev->next) {
ListNode *prev2 = &dummy;
while (prev2 != prev && prev2->next->val < prev->next->val) { // 找到插入位置: prev2->next
prev2 = prev2->next;
}
if (prev2 != prev) { // 可插入
ListNode *cur = prev->next;
prev->next = prev->next->next;
cur->next = prev2->next;
prev2->next = cur;
} else { // 当前节点及前方节点有序
prev = prev->next;
}
}
return dummy.next;
}
```
##### 归并排序
自顶向下递归：
- **拆分成均等的两段链表**
- **==递归==地将两段链表分别排序**，再 "**合并两条有序链表**"
```cpp
// 思路一: 自顶向下递归的归并排序
class Solution1 {
public:
ListNode* merge_two_lists(ListNode* list1, ListNode* list2) {
if (!list1) return list2;
if (!list2) return list1;
ListNode dummy(0), *prev = &dummy;
while (list1 && list2) {
if (list1->val <= list2->val) {
prev->next = list1;
list1 = list1->next;
} else {
prev->next = list2;
list2 = list2->next;
}
prev = prev->next;
}
prev->next = list1 ? list1 : list2;
return dummy.next;
}
ListNode* sortList(ListNode* head) {
if (!head || !head->next) return head;
ListNode *slow = head, *fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
ListNode* new_head = slow->next;
slow->next = nullptr;
return merge_two_lists(sortList(head), sortList(new_head));
}
};
```
自底向上归并：
```cpp
// 思路二: 自底向上迭代的归并排序
class Solution2 {
public:
ListNode* sortList(ListNode* head) {
if (!head || !head->next) return head;
int n = getLength(head);
ListNode dummy(0, head), *prev = &dummy;
int seq = 1;
while (seq < n) {
ListNode *prev = &dummy, *rest = dummy.next;
while (rest) {
ListNode *h1 = rest;
ListNode *h2 = cutListHead(h1, seq);
rest = cutListHead(h2, seq);
prev->next = mergeTwoList(h1, h2);
while (prev->next) {
prev = prev->next;
}
}
seq *= 2;
}
return dummy.next;
}
ListNode* mergeTwoList(ListNode* list1, ListNode* list2) {
if (!list1) return list2;
if (!list2) return list1;
ListNode dummy(0), *prev = &dummy;
while (list1 && list2) {
if (list1->val <= list2->val) {
prev->next = list1;
list1 = list1->next;
} else {
prev->next = list2;
list2 = list2->next;
}
prev = prev->next;
}
prev->next = list1 ? list1 : list2;
return dummy.next;
}
ListNode* cutListHead(ListNode* head, int len) {
if (len <= 0) return head;
int step = len - 1;
while (head && step--) {
head = head->next;
}
if (head) {
ListNode* rest = head->next;
head->next = nullptr;
return rest;
}
return nullptr;
}
int getLength(ListNode* head) {
int n = 0;
for (; head; ++n, head = head->next);
return n;
}
};
```
<br>
# 相交链表
> 参见 [[99-题解/leetcode/lc-160 相交链表|lc-160 相交链表]]
<br><br>
# 环形链表专题
> 参见 [[99-题解/leetcode/lc-141 环形链表|lc-141 环形链表]]、[[99-题解/leetcode/lc-142 环形链表II|lc-142 环形链表II]]
系列问题：
- 判断链表**是否有环**
- 求链表中**环的入口节点**
- 求环形链表中的**环长**、**直链长度**，**链表总长**
## （1）判断环形链表
![[Excalidraw-Solution/链表_0.excalidraw.svg|335]]
%%[[Excalidraw-Solution/链表_0.excalidraw.md|🖋 Edit in Excalidraw]]%%
#### 方法
快慢指针从原点开始走，**快指针每次走 2 步，慢指针每次走 1 步**，若链表有环，**则两指针最终必然相交**，且相交时**慢指针还未走完环的一圈**。
#### 证明
如果存在环，快指针 `fast` 一定会先进入环中。当**慢指针 `slow` 进入环中时，两指针距离 $d$ 小于环长 $c$**。
由于慢指针步长为 1，快指针步长为 2，**因此每走一步，==二者间的距离减 1==**，所以，**在慢指针 `slow` 走完第一圈前，必然会被快指针 `fast` 追上，故==二者必定会相遇==**。
#### 扩展
> [!faq] ❓若快慢指针的**步长分别为 `f` 、`s`**，则**两指针是否可能相遇？即能否用以判断环形链表**？
具体取决于 **"二者步长差值 `f-s`"**、**"环长 `c`"**、**"慢指针入环时二者的初始距离 `d`"** 三个因素。
**若两指针能够相遇，假设慢指针入环后，二者行走 `k` 步后相遇，则有等式 $fk-sk=nc+d$ 成立，其中 `n` 为快指针多走的圈数**。
在已知 $f,s,d,c$ 时，上式是**关于 `k` 与 `n` 的二元一次方程**，**若存在==整数解== `k` 与 `n` 使上式成立，则两指针能够相遇**。
> [!example] 一些反例
>
> - $s=1$，$f=c+1$，即**慢指针步长为 1，快指针步长为环长+1，则只要慢指针入环时二者距离 $d\neq 0$，则两指针始终保持初始距离 $d$，永远不可能相遇**。
> - 代入式子 $fk-sk=nc+d$，得到 $kc=nc+d$，因此除非 $d==0$，否则无解。
>
>>
>
> - $s=3$，$f=c=6$，**则慢指针每次落脚点只有两个：初始位置&相较于初始位置的半环长**； **快指针落脚点只有一个：初始位置**，**如果两指针的落脚点无重合，则永不可能相遇**。
> - 代入式子 $fk-sk=nc+d$，得到 $3k=3n+d$，由于 $d< c=6$， 因此除非 $d==0$ 或 $d==3$，否则无解。
>
>>
>
> - $s=2$，$f=4$，则每次移动时**二者间距离-2**，取决于两指针**在环内的距奇偶性**，
> - 若**距离为偶数**，则快指针必然能追上慢指针；
> - 若**距离为奇数**，则最后两指针会相邻，再下一步**快指针越过慢指针**，二者**间距始终为奇数**，无法相遇。
<br><br>
## （2）求环形链表的入口节点
#### 方法
1. 快慢指针从原点开始走，**快指针每次走 2 步，慢指针每次走 1 步**，若链表有环，**则两指针最终必然相遇**。
2. **快慢指针首次相交后**，**慢指针 `s1`从该==相交点==起始继续每次走一步**，**另一个慢指针 `s2` 从==链表头==起始每次也走一步**，当 `s1` 与 `s2` 相交时，**二者所指向的即为==链表入口节点==**。
#### 证明
![[Excalidraw-Solution/链表_2.excalidraw.svg|417]]
%%[[Excalidraw-Solution/链表_2.excalidraw.md|🖋 Edit in Excalidraw]]%%
已知快慢指针必然会相遇，且**二者相遇时慢指针还未走完 1 圈**。
相遇时，**快指针所走路长为慢指针的两倍**，故有等式：$L+nc+d=2(L+d)$ 成立，其中 $n\geq 0$ 是**快指针多走的圈数**。
**移项得到 $L=nc-d$**，即当**慢指针 `s1` 从相交点开始走，距离走完第 $n$ 圈还差 $d$ 长度时**（此时**慢指针==恰落在环入口点==**，见上图），**其走过的距离恰为 $L$**。
因此，**令第二个慢指针 `s2` 从链表头开始走，==走完 $L$ 长度==后**，**两指针 `s1` 与`s2` ==恰好同时落在环入口节点==**，即**两指针 "==相遇点==" 即为环入口点**。
<br>
## （3）求环形链表中各段长度，总长
#### 方法
- 采用 "**求环的入口节点**" 的方法，从**链表头走到入口节点**，得到 "**直链部分**" 的长度 $L$。
- 从**环入口节点**起始，每次走一步，**绕圈回到入口处可得到环长** $C$。
<br><br>
# 参考资料
# Footnotes