【数据结构】顺序表和链表——链表（包含大量经典链表算法题）

1. 单链表

1.1 概念与结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

淡季时车次的车厢会相应减少，旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉/加上，不会影响其他车厢，每节车厢都是独立存在的。

在链表里，每节“车厢”是什么样的呢？

1.1.1 结点

与顺序表不同的是，链表里的每节"车厢"都是独立申请下来的空间，我们称之为“结点/节点”

结点的组成主要有两个部分：当前结点要保存的数据和保存下一个结点的地址（指针变量）。

图中指针变量plist保存的是第一个结点的地址，我们称plist此时“指向”第一个结点，如果我们希望plist“指向”第二个结点时，只需要修改plist保存的内容为0x0012FFA0即可。

链表中每个结点都是独立申请的（即需要插入数据时才去申请一块结点的空间），我们需要通过指针变量来保存下一个结点位置才能从当前结点找到下一个结点。

1.1.2 链表的性质

1、链式结构在逻辑上是连续的，在物理结构上不⼀定连续

2、结点一般是从堆上申请的

3、从堆上申请来的空间，是按照一定策略分配出来的，每次申请的空间可能连续，可能不连续

结合前面学到的结构体知识，我们可以给出每个结点对应的结构体代码：

假设当前保存的结点为整型：

struct SListNode
{int data; //结点数据struct SListNode* next; //指针变量⽤保存下⼀个结点的地址
};

当我们想要保存一个整型数据时，实际是向操作系统申请了一块内存，这个内存不仅要保存整型数据，也需要保存下⼀个结点的地址（当下⼀个结点为空时保存的地址为空）。

当我们想要从第一个结点走到最后一个结点时，只需要在当前结点拿上下一个结点的地址就可以了。

1.1.3 链表的打印

给定的链表结构中，如何实现结点从头到尾的打印？

思考：当我们想保存的数据类型为字符型、浮点型或者其他⾃定义的类型时，该如何修改？

1.2 实现单链表

SList.h

typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data; //结点数据struct SListNode* next; //指针保存下一个结点的地址
}SLTNode;void SLTPrint(SLTNode* phead);
//头部插入删除/尾部插入删除
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);//查找
SLTNode * SLTFind(SLTNode* phead, SLTDataType x);
//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDestroy(SLTNode** pphead);

上面这部分是链表实现所需要的节点结构和一些方法，其中具体的方法由读者自己先来尝试实现，如有不会的可以在讨论区询问，将会由作者或者其它积极的读者来解答❤️❤️❤️

1.3 链表的分类

链表的结构非常多样，以下情况组合起来就有8种（2 x 2 x 2）链表结构：

链表说明：

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：单链表和双向链表

1. 无头单向非循环链表（俗称：单链表）：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2. 带头双向循环链表（俗称：双向链表）：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

1.4 单链表算法题

1.4.1 移除链表元素

https://leetcode.cn/problems/remove-linked-list-elements/description/

OJ代码有bug怎么办？VS调试技能用起来

（1）将OJ代码复制粘贴到vs上

（2）创建测试方法，调用本次要调试的目标方法

（3）利用vs调试工具排查代码问题

1.4.2 反转链表

https://leetcode.cn/problems/reverse-linked-list/description/

1.4.3 链表的中间结点

https://leetcode.cn/problems/middle-of-the-linked-list/description/

1.4.4 合并两个有序链表

https://leetcode.cn/problems/merge-two-sorted-lists/description/

1.4.5 链表分割

https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70

1.4.6 链表的回文结构

https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa

1.4.7 相交链表

https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

1.4.8 环形链表1

https://leetcode.cn/problems/linked-list-cycle/description/

💡 快慢指针

快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表起始位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的未尾

思考1：为什么快指针每次走两步，慢指针走一步可以相遇，有没有可能遇不上，请推理证明！

slow一次走一步，fast一次走2步，fast先进环，假设slow也走完入环前的距离，准备进环，此时fast和slow之间的距离为N，接下来的追逐过程中，每追击一次，他们之间的距离缩小1步

追击过程中fast和slow之间的距离变化：

因此，在带环链表中慢指针走一步，快指针走两步最终一定会相遇。

思考2：快指针一次走3步，走4步，…n步行吗?

step1:

按照上面的分析，假设慢指针每次走一步，快指针每次走三步，此时快慢指针的最大距离为N，接下来的追逐过程中，每追击一次，他们之间的距离缩小2步

追击过程中fast和slow之间的距离变化：

分析:

（1）如果N是偶数，第一轮就追上了

（2）如果N是奇数，第一轮追不上，快追上，错过了，距离变成-1，即C-1，进入新的一轮追击

​ a、C-1如果是偶数，那么下一轮就追上了

​ b、C-1如果是奇数， 那么就永远都追不上

总结一下追不上的前提条件： N是奇数，C是偶数

但是你以为就是这样吗？请看下面进一步分析

step2:

假设：

环的周长为C，头结点到slow结点的长度为L，slow走一步，fast走三步，当slow指针入环后，

slow和fast指针在环中开始进行追逐，假设此时fast指针已经绕环x周。

在追逐过程中，快慢指针相遇时所走的路径长度:

fast：$L+x\ast C+C-N$

slow：$L$

由于慢指针走一步，快指针要走三步，因此得出： $3\ast 慢指针路程=快指针路程$，即：

$3L=L+x\ast C+C-N$

化简得：$2L=(x+1)C-N$

对上述公式继续分析：由于偶数乘以任何数都为偶数，因此 $2L$ 一定为偶数，则可推导出这个可能的情况：

• 情况1：偶数 = 偶数 - 偶数

• 情况2：偶数 = 奇数 - 奇数

由step1中（1）得出的结论，如果N是偶数，则第一圈快慢指针就相遇了。

由step1中（2）得出的结论，如果N是奇数，则fast指针和slow指针在第一轮的时候套圈了，开始进行下一轮的追逐；当N是奇数，要满足以上的公式，则 $(x+1)C$ 必须也要为奇数

• 其中如果C为偶数，则这里的$(x+1)C$ 为偶数，条件不满足，则step1中（2）b的C-1为奇数不存在。

• 如果C为奇数，满足这里的$(x+1)C$ 为奇数且符合step1中（2）a的C-1为偶数的结论，则快慢指针会相遇。

因此， step1中的 N是奇数，C是偶数不成立 ，既然不存在该情况，则快指针一次走3步最终一定也可以相遇。

快指针一次走4、5…步最终也会相遇，其证明方式同上。

typedef struct ListNode ListNode;
bool hasCycle(struct ListNode* head) {ListNode * slow, * fast;slow = fast = head;while (fast && fast->next){slow = slow->next;int n = 3; //fast每次⾛三步while (n--){if (fast->next)fast = fast->next;elsereturn false;}if (slow == fast){return true;}}return false;
}

💡 提示

虽然已经证明了快指针不论走多少步都可以满足在带环链表中相遇，但是在编写代码的时候选择其它的步数方式会有额外的步骤引入，所以涉及到快慢指针的算法题中通常习惯使用慢指针走一步快指针走两步的方式。

1.4.9 环形链表2

https://leetcode.cn/problems/linked-list-cycle-ii/description/

💡 结论

让一个指针从链表起始位置开始遍历链表,同时让一个指针从判环时快慢指针相遇点的位置开始绕环运行,两个指针都是每次均走一步,最终肯定会在入口点的位置相遇。

证明以上结论：

说明:

​ H为链表的起始点，E为环入口点，M与判环时候相遇点。

假设:

​ 环的长度为R，H到E的距离为L，E到M的距离为 X ，则：M到E的距离为 R-X。

在判环时,快慢指针相遇时所走的路径长度:

fast: $L+X+nR$

slow：$L+X$

注意:

1.当慢指针进入环时，快指针可能已经在环中绕了n圈了，n至少为1

​ 因为：快指针先进环走到M的位置，最后又在M的位置与慢指针相遇

2.慢指针进环之后，快指针肯定会在慢指针走一圈之内追上慢指针

​ 因为：慢指针进环后，快慢指针之间的距离最多就是环的长度,而两个指针在移动时,每次它们至少距离都缩减一步，因此在慢指针移动一圈之前快指针肯定是可以追上慢指针的，而快指针速度是慢指针的两倍，因此有如下关系是：

$2\ast (L+X)=L+X+nR$

—>$L+X=nR$

—>$L=nR-X$

—>$L=(n-1)R+(R-X)$

(n为1,2,3,4…，n的大小取决于环的大小，环越小n越大)

极端情况下，假设n=1，此时： L=R-X

即：一个指针从链表起始位置运行，一个指针从相遇点位置绕环，每次都走一步，两个指针最终会在入口点的位置相遇。

1.4.10 随机链表的复制

https://leetcode.cn/problems/copy-list-with-random-pointer/description/

更多链表算法刷题入口：

牛客网：https://www.nowcoder.com/exam/oj

LeetCode：https://leetcode.cn/problems/copy-list-with-random-pointer/description/

2. 双向链表

2.1 概念与结构

💡注意

这里的“带头”跟前面我们说的“头结点”是两个概念，实际前面的在单链表阶段称呼不严谨，但是为了同学们更好的理解就直接称为单链表的头结点。

带头链表里的头结点，实际为“哨兵位”，哨兵位结点不存储任何有效元素，只是站在这里“放哨的”

2.2 实现双向链表

List.h

typedef int LTDataType;
typedef struct ListNode
{struct ListNode* next; //指针保存下⼀个结点的地址struct ListNode* prev; //指针保存前⼀个结点的地址LTDataType data;}LTNode;//void LTInit(LTNode** pphead);
LTNode * LTInit();
void LTDestroy(LTNode* phead);
void LTPrint(LTNode* phead);
bool LTEmpty(LTNode* phead);
void LTPushBack(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);
void LTPushFront(LTNode* phead, LTDataType x);
void LTPopFront(LTNode* phead);
//在pos位置之后插⼊数据
void LTInsert(LTNode* pos, LTDataType x);
void LTErase(LTNode* pos);
LTNode* LTFind(LTNode* phead, LTDataType x);

上面这部分是链表实现所需要的节点结构和一些方法，其中具体的方法由读者自己先来尝试实现，如有不会的可以在讨论区询问，将会由作者或者其它积极的读者来解答❤️❤️❤️

3. 顺序表与链表的对比分析