链表

OYH2025年4月14日大约 4 分钟

链表

有关链表的基础结构，我已经写在了博客的数据结构栏目里，具体的 C++ 代码可以查看仓库。ref

链表里面涉及的算法主要是双指针和递归。

链表数据在内存里不是连续分布的，而是离散分布，通过指针指向另外一个内存地址。也就是说，我只要知道了一个链表头结点的地址，我就能依次拎起整个链表，而不需要像数组那样，把整个数据块都告诉我。但是也由于链表的指针特性，导致链表只能单向查找 （或者构建双向链表实现双向的查找），链表查找数据的时间复杂度达到了 $O(n)$ 。

节点数据结构定义

我用 python 用得比较多，但是 python 里面没有指针的概念，所以在定义头结点的时候，需要直接把self.next赋值为一个ListNode类型的变量，也就是说直接把下一个节点赋值给他。

class ListNode:
    def __init__(self, val=0, next: ListNode=None):
        self.val = val
        self.next = next

虚拟头结点

为了方便使用递归，使得我们在处理链表时，不需要对头结点额外做处理，我们往往会创建一个虚拟头结点，这个虚拟头结点的next指针指向链表的头结点，这个虚拟节点包含的值是什么不重要，重要的是其指针指向了头结点，可以说消除了头结点的特殊性。

双指针

这个在数组里就见到过很多次了，最麻烦的题是环形链表 II，这个看解析说得很清楚了，这里不做记录。双指针的好处是可以降低时间复杂度，一般能把 $O(n^2)$ 的时间复杂度降低到 $O(n)$

环形链表模型

环形链表的题可以抽象为一种母模型，涉及到通过一种固定操作就能完成状态循环的题目，可以优先考虑快慢指针，快指针向前移动 2 个状态，慢指针再向前移动 1 个状态，直到二者相遇，确定相遇状态点。“成环”代表达成了一种状态的循环，这个是关键。他可以用来判断状态转换是否达成了循环，应该算是一种特殊的状态机算法（还没学到，学到了再来补充）。

例：快乐数中等这题里的快乐数，就是一种状态的循环，考虑用快慢指针法解决。

递归

在对链表进行操作的时候，包括连续插入，打印链表值等需要循环操作的过程，我们通过递归能够使代码变得简洁。但是递归很容易被绕晕，最有效的防止晕递归的方法是：在写好代码之前不要让思绪陷入递归树中，而是直接考虑递归函数作为整体完成了什么步骤。

递归的学习可以看五点七边up 主的系列视频，讲的很细致。

我认为最重要的是第二集，递归的组成部分有三：基础情况调用、递归函数调用、递推到当前层。在设计递归算法的时候，可以先从最简单的情况开始考虑，慢慢往上加数量，变得更难，然后从中发现能够被重复操作、具有相似特性的操作，将其放入递归调用中，也就是视频里提到的超级操作，在这一步，不用去考虑里面的具体实现，而是应该相信这一步能够做到我们要他做的事情，然后将其视作一个整体组织代码顺序。

链表里目前碰到的递归有：

24.两两交换链表中的节点中等
打印链表：可以采用递归的形式实现

别急，链表里的递归都是简单的，等到了动态规划才有的受。

贡献者

dream-oyh