2.1 链表概述

2.1.1 链表的定义

和数组一样，链表也主要用于存储序列数据[ a ₀ ， a ₁ ，…， a _{n -1} ]。通常一个链表由若干结点构成，每个结点存储一个序列元素，这些结点的地址既可以是连续的也可以是不连续的，每个结点通过指针域表示元素之间的序列关系。链表分为单链表、双链表和循环链表等，除了特别说明外，默认指针指的是单链表。其结点类型声明如下。

C++：

Python：

单链表分为不带头结点和带头结点两种形式，在LeetCode中给定的单链表一般是不带头结点的。例如，head=[1，3，2，4]，其不带头结点的单链表如图2.1所示，head为首结点的地址，结点的序号依次为0～3。

带头结点的单链表通过头结点地址标识，其中头结点不存储序列元素，头结点的next域指向首结点，这样保证了每个序列结点都有一个前驱结点，从而简化了算法设计。例如，head=[1，3，2]，其带头结点的单链表如图2.2所示，head为头结点的地址。

2.1.2 链表的知识点

本小节的单链表h均为带头结点的单链表， n 个数据结点的序号依次为0～ n -1，头结点的序号看成-1，如图2.2所示。

1.查找序号为i的结点

在查找操作中序号 i 的有效范围是-1～ n -1，当 i =-1时返回头结点；当0≤ i ≤ n -1时返回序号为 i 的结点的地址。查找过程是先置 j =0，p指向首结点（ j 和p配合使用表示结点p的序号为 j ，初始时表示首结点的序号为0），在 j ＜ i 时循环执行 j ++和p=p- next语句，直到 j = i 为止，此时p恰好指向序号为 i 的结点，如图2.3所示，找到后返回p即可。当 i 无效时返回NULL（即 i ≥ n 时超界）。

查找算法如下。

C++：

Python：

2.插入值为x的结点作为序号为i的结点

在插入操作中序号 i 的有效范围是0～ n 。当 i 有效时，先调用geti（ i -1）找到序号为 i -1的结点p（即插入结点的前驱结点），新建存放 x 的结点s，并在结点p之后插入结点s，如图2.4所示。当 i 无效时不改变单链表。

插入算法如下。

C++：

Python：

3.删除序号为i的结点

在删除操作中序号 i 的有效范围是0～ n -1。先调用geti（ i -1）找到序号为 i -1的结点p（即删除结点的前驱结点），当p不为空时（说明此时 i 是有效的），通过结点p删除其后继结点s，如图2.5所示。当 i 无效时不改变单链表。

删除算法如下。

C++：

Python：

说明： 在单链表中插入或者删除一个结点时需要先找到前驱结点，通过修改前驱结点的next指针实现结点的插入或者删除。

4.用头插法建表

用头插法建表就是先创建头结点h，并将其next指针设置为空（相当于建立一个空链表），每次创建一个新结点s，并将结点s插入表头，如图2.6所示。所以用头插法创建的单链表的结点值顺序与数据序列的顺序相反。

由 a [0.. n -1]用头插法建表的算法如下。

C++：

Python：

5.用尾插法建表

用尾插法建表就是先创建头结点h，并设置尾指针r（初始时指向头结点h），每次创建一个新结点s，并将结点s插入表尾，如图2.7所示，最后将尾结点的next域置为空。所以用尾插法创建的单链表的结点值顺序与数据序列的顺序相同。

由 a [0.. n -1]用尾插法建表的算法如下。

C++：

Python：

6.两个有序链表的合并

给定两个递增有序单链表h1和h2，将所有结点合并为一个递增有序单链表h，要求不破坏单链表h1和h2的结点。

使用二路归并+尾插法建表的过程如下。

（1）新建空链表h，用p和q分别遍历h1和h2。

（2）当p和q均未遍历完时循环：若结点p的值较小，则归并结点p，即由结点p复制产生新结点s，将结点s链接到链表h的末尾，向后移动指针p；若结点q的值较小，则归并结点q，即由结点q复制产生新结点s，将结点s链接到链表h的末尾，向后移动指针q。

（3）将p或者q中未遍历完的结点归并到链表h的末尾。

（4）将尾结点r的next域置为空，返回合并后的结果单链表h。

对应的算法如下。

C++：

Python： Cvu4U/doorS84vafLAfHZKtzHVm5iYNWgumUpbm6gg3rz8zlNcJBXxlC3zDcxYQ9