一、链表基础知识
1. 链表概念
- 链表是一种常见的基础数据结构。在链表中，每个节点包含指向下一个节点的指针，这些指针把节点连接成链状结构。
2. 哨兵节点
- 哨兵节点是为了简化处理链表边界条件而引入的附加链表节点。哨兵节点通常位于链表的头部，它的值没有任何意义，他可以简化代码的逻辑（非代码效率），如节点判空或头节点值判断等逻辑不需要再单独编写。在一个有哨兵节点的链表中，从第2个节点开始才真正保存有意义的信息。
二、链表知识扩展
1. 链表中的双指针
- 前后双指针：寻找链表中倒数第
i个元素，可以通过右指针先移动i-1次后，左右指针一起移动，直到右指针到达最右侧，左指针所指向的节点即倒数第i个元素。 - 快慢指针：左右指针以不同的速度向后移动，右指针如果左指针移动速度的两倍，当右指针到达最右侧时，左指针刚好处于中间位置。
链表题目 | 双指针
题目一：删除倒数第k个节点
如果给定一个链表，请问如何删除链表中的倒数第 k个节点？假设链表中节点的总数为n，那么1≤k≤n。要求只能遍历链表一次。例如，输入图4.1(a)中的链表，删除倒数第2个节点之后的链表如图4.1(b)所示。
题目分析
难度： ⭐
思路： 典型的前后双指针题目，在右指针移动到最右侧时，删除左指针的元素即可。
参考代码
Tips：2023-11-14 10:22
题目二：链表中环的入口节点
如果一个链表中包含环，那么应该如何找出环的入口节点？从链表的头节点开始顺着next指针方向进入环的第1个节点为环的入口节点。例如，在如图4.3所示的链表中，环的入口节点是节点3。
题目分析
难度： ⭐⭐
思路： 题目可通过结合双指针的两种使用方式实现目的。
解法一，将问题拆分为三个子问题：
1. 是否存在环链：快指针以慢制作的两倍速度移动，如果快慢指针相遇，则说明存在环。
2. 确定环节点长度m：快慢指针相遇的节点一定在环内，以该节点起，遍历下一个节点，当再次遍历到该节点，中间经过的节点数即环的长度。
3. 获取链倒数第m个元素：通过前后双指针获取倒数第m个节点元素。
解法二，基于解法一，省去获取环节点数的步骤：
通过仔细分析，不难发现并没有必要求得环中节点的数目。如果链表中有环，快慢两个指针一定会在环中的某个节点相遇。慢的指针一次走一步，假设在相遇时慢的指针一共走了k步。由于快的指针一次走两步，因此在相遇时快的指针一共走了2k步。因此，到相遇时快的指针比慢的指针多走了k步。另外，两个指针相遇时快的指针比慢的指针在环中多转了若干圈。也就是说，两个指针相遇时快的指针多走的步数k一定是环中节点的数目的整数倍，此时慢的指针走过的步数k也是环中节点数的整数倍。
此时可以让一个指针指向相遇的节点，该指针的位置是之前慢的指针走了k步到达的位置。接着让另一个指针指向链表的头节点，然后两个指针以相同的速度一起朝着指向下一个节点的指针移动，当后面的指针到达环的入口节点时，前面的指针比它多走了k步，而k是环中节点的数目的整数倍，相当于前面的指针在环中转了k圈后也到达环的入口节点，两个指针正好相遇。也就是说，两个指针相遇的节点正好是环的入口节点。
参考代码
Tips：2024-01-21 01:01
题目三：两个链表的第1个重合节点
输入两个单向链表，请问如何找出它们的第1个重合节点。例如，图4.5中的两个链表的第1个重合节点的值是4。
题目分析
难度： ⭐
思路： 根据链表的特性，不难发现，在节点重合后不可能在分叉，即链表起点可能不一样，但重点绝对一样。可以以两链表的长度差为前后双指针距离差，左指针指向长的链首节点，右指针从短链首节点，左指针移动长度差距离后，左右指针开始一起移动，当左右指针指向的值为同一个的时候，所指向的节点即为所求。
参考代码
Tips：2024-01-21 01:02
2. 反转链表
- 单项链表最大的特点就是其单向性，只能单向遍历，有时在处理部分问题时，将链表反转（首尾依次交换）后会更加的容易解决。而如何反转链表，也是一类常见的问题。
链表题目 | 反转链表
题目一：反转链表
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。例如，把图4.8(a)中的链表反转之后得到的链表如图4.8(b)所示。
题目分析
难度： ⭐
思路： 反转，即将节点指向下一个节点的指针指向上一个节点，但由于修改指向后，下一个节点会丢失，所以可以使用一个临时变量存储下一个节点。假如当前已经处理到第j个节点，i是其上一个节点，k是其下一个节点，此时用一个临时节点保存k节点，然后将j节点指向i节点，最后又对临时节点进行想同处理，直到不再有下一个节点为止。
参考代码
Tips：2024-01-21 01:03
题目二：链表中的数字相加
给定两个表示非负整数的单向链表，请问如何实现这两个整数的相加并且把它们的和仍然用单向链表表示？链表中的每个节点表示整数十进制的一位，并且头节点对应整数的最高位数而尾节点对应整数的个位数。例如，在图4.10(a)和图4.10(b)中，两个链表分别表示整数123和531，它们的和为654，对应的链表如图4.10(c)所示。
题目分析
难度： ⭐
思路： 题目容易忽略的问题是进位以及两链表长度不同时，应按位加（倒序），步骤如下：
1. 将两个链表反转，反转后的链表；
2. 从首节点开始依次做加法运算，进位记录到临时变量中，下一节点进行运算时将进位也加入到运算并清除变量；
3. 将运算结果链表反转。
参考代码
Tips：2024-01-21 01:04
题目三：重排链表
给定一个链表，链表中节点的顺序是L0 → L1 → L2 → … → Ln-1 → Ln，请问如何重排链表使节点的顺序变成L0 → Ln → L1 → Ln-1→ L2 → Ln-2 → …？例如，输入图 4.12(a)中的链表，重排之后的链表如图4.12(b)所示。
题目分析
难度： ⭐
思路： 通过观察不难发现，所求链表的元素即按首尾依次各取一个元素放入新的链表中，剩余的元素重复该操作，直到操作次数达到链表长度的一半为止。所以可以通过将链表反转，通过原链表和反转后的链表依次取值，直到到达链表的中心点为止（在反转的过程中记录下链表的长度，避免重复遍历）。
参考代码
Tips：2024-01-21 01:05
题目四：回文链表
如何判断一个链表是不是回文？要求解法的时间复杂度是O(n)，并且不得使用超过O(1)的辅助空间。如果一个链表是回文，那么链表的节点序列从前往后看和从后往前看是相同的。例如图4.13中的链表的节点序列从前往后看和从后往前看都是1、2、3、3、2、1，因此这是一个回文链表。
题目分析
难度： ⭐⭐
思路： 如果不考虑O(1)辅助空间的限制，那么将链表反转后，使用一个O(n)的辅助控件进行存储，再和原链表一一进行比较即可。开了到到辅助空间的限制，可以直接对原链表进行反转，但不完全反转链表。首先遍历一次获取链表长度，随后对原链表进行反转，在反转到一半的时候停止，此时左右节点同时忘两边遍历，一一比较即可，需要注意的是奇数和偶数两次情况的处理略有不同
参考代码
Tips：2024-01-21 01:06
3. 双向链表和循环链表
- （待补充）
链表题目 | 双向链表和循环链表
题目一：展平多级双向链表
在一个多级双向链表中，节点除了有两个指针分别指向前后两个节点，还有一个指针指向它的子链表，并且子链表也是一个双向链表，它的节点也有指向子链表的指针。请将这样的多级双向链表展平成普通的双向链表，即所有节点都没有子链表。例如，图4.14(a)所示是一个多级双向链表，它展平之后如图4.14(b)所示。
题目分析
难度： ⭐
思路： 根据题意，可以注意到，这是一个比较经典的递归问题；当发现节点存在其他链的指针时，暂存下一个节点数据，通过递归的方式处理其他链的数据。在所有的链都处理完后，再将处理好的节点继续只想上一步暂存的节点即可。
参考代码
Tips：2024-01-21 01:07
题目二：排序的循环链表
在一个循环链表中节点的值递增排序，请设计一个算法在该循环链表中插入节点，并保证插入节点之后的循环链表仍然是排序的。例如，图4.15(a)所示是一个排序的循环链表，插入一个值为4的节点之后的链表如图4.15(b)所示。
题目分析
难度： ⭐
思路： 遍历节点时，如果下一个节点和当前节点是顺序的，只需要判断是否满足新值在其中见即可；如果不是顺序的，判断是否满足值大于当前节点或者小于下一个节点即可；需要注意的是，存在特殊情况，即链表只存在一个节点或者是空链表。
参考代码
Tips：2024-01-21 01:08
三、章节小结
略