2.2 链表基本操作的算法设计

链表的基本操作包括结点的遍历、插入和删除等，本节的求解算法主要基于这些基本操作实现。

2.2.1 LeetCode203——移除链表元素★

【问题描述】 给定一个链表head和一个整数val，删除链表中所有满足值为val的结点，并返回新链表的首结点。

例如，head=[1，2，3，1，2，5]，val=2，删除后head=[1，3，1，5]，如图2.8所示（带阴影的结点为被删结点）。

【限制】 链表的结点数目在[0，10 ⁴ ]范围内，1≤Node.val≤50，0≤val≤50。

【解法1】 直接删除法。先在单链表head中从头到尾找到第一个不等于val的结点p。若p=NULL，说明所有结点的值均为val，则返回NULL。

在p≠NULL时循环：用同步指针（pre，p）遍历剩余的结点，若p结点的值等于val，则通过pre结点删除结点p，此时保持pre不变，让p指向结点pre的后继结点后继续循环，否则pre和p同步后移一个结点后继续循环。循环完毕返回head。

【解法2】 用尾插法建表。创建一个带头结点的空单链表h，r作为尾结点指针，用p遍历head，将要保留的结点p（结点值不为val的结点）链接到h的末尾，遍历完毕将结点r的next域置为空，最后返回h- next。注意这里没有释放被删除结点的空间，在Python中可以不必这样做，因为系统会自动回收这些空间。而在C++中需要专门编写相应的代码完成回收工作，否则尽管程序运行正确但可能会造成内存泄漏。

2.2.2 LeetCode206——反转链表★

【问题描述】 给定一个单链表head，请反转该链表并返回反转后的链表。

例如，head=[1，2，3，4，5]，反转后head=[5，4，3，2，1]，如图2.9所示。

【限制】 链表的结点数目在[0，5000]范围内，-5000≤Node.val≤5000。

【解题思路】 用头插法建表。先创建一个带头结点的空单链表h作为结果单链表，用p遍历head，将结点p插入h的表头，最后返回h- next即可。对应的算法如下。

C++：

提交运行：

Python：

提交运行：

2.2.3 LeetCode328——奇偶链表★★

【问题描述】 给定一个单链表head，将所有索引为奇数的结点和所有索引为偶数的结点分别组合在一起，然后返回重新排序的列表。第一个结点的索引被认为是奇数，第二个结点的索引被认为是偶数，以此类推。注意偶数组和奇数组内部的相对顺序应该与输入时保持一致。另外，必须在 O （1）的额外空间复杂度和 O （ n ）的时间复杂度下解决这个问题。

例如，head=[1，2，3，4，5]，按奇、偶序号重排后的链表为head=[1，3，5，2，4]，如图2.10所示。

【限制】 链表的结点数目在[0，10 ⁴ ]范围内，-10 ⁶ ≤Node.val≤10 ⁶ 。

【解题思路】 用尾插法建表。这里以head=[1，2，3，4，5]为例说明按奇、偶序号重排链表的过程：

（1）创建奇序号链表的头结点h1和尾结点指针r1，创建偶序号链表的头结点h2和尾结点指针r2。

（2）遍历head，将奇序号的结点p链接到h1的末尾，将偶序号的结点p链接到h2的末尾。遍历完毕h1=[1，3，5]，h2=[2，4]。

（3）将h1的尾部与h2的首部相链接，即r1- next=h2- next。

（4）将尾结点r2的next域置为空，得到h1=[1，3，5，2，4]，返回h1- next即可。

对应的算法如下。

C++：

提交运行：

Python：

提交运行：

2.2.4 LeetCode61——旋转链表★★

【问题描述】 给定一个链表head，将该链表中的每个结点向右移动 k 个位置。

例如，head=[1，2，3，4，5]， k =3，旋转结果为head=[3，4，5，1，2]，旋转过程如图2.11所示。

【限制】 链表中结点的数目在[0，500]范围内，-100≤Node.val≤100，0≤ k ≤2×10 ⁹ 。

【解题思路】 简单遍历法 。假设head中包含 n 个结点，将后面 k 个结点循环移动到表头，显然移动后新的表首结点是序号为 n - k 的结点，先将整个单链表变为循环单链表，找到原序号为 n - k -1的结点p，将head指向结点p的后继结点，在结点p和结点head之间断开（将结点p作为尾结点），返回head即可。这里以head=[1，2，3，4，5]， k =3为例说明旋转过程：

（1）遍历head，直到p指向尾结点为止，同时求出单链表的结点个数 n =5。执行p->next=head将其构成一个循环单链表，如图2.12（a）所示。

（2）当 k ＜ n 时，直接向右移动 k 个位置。当 k ≥ n 时，向右移动 k 个位置等同于向右移动 k % n 个位置，不妨置 k = k % n =3。求出 m = n - k =2，此时向右移动 k 个位置等同于p从head开始后移 m -1步，如图2.12（b）所示。

（3）在结点p和结点head之间断开，即置p->next=NULL，如图2.12（c）所示，此时的head为旋转后的结果单链表。

对应的算法如下。

C++：

提交运行：

Python：

提交运行：

2.2.5 LeetCode141——环形链表★

【问题描述】 给定一个链表head，判断该链表中是否有环。如果链表中有某个结点，可以通过连续跟踪next指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾链接到链表中的位置（索引从0开始）。注意，pos不作为参数进行传递，仅是为了标识链表的实际情况。如果链表中存在环，则返回true，否则返回false。

例如，head=[3，2，0，-4]，pos=1，该链表如图2.13所示，其中有一个环，其尾部连接到序号为1的结点，返回true。

【限制】 链表中结点数目 n 的范围是[0，10 ⁴ ]，-10 ⁵ ≤Node.val≤10 ⁵ ，pos为-1（表示没有环）或者为链表中的一个有效索引（0～ n -1）。

【解题思路】 快慢指针遍历法 。设置快指针fast和慢指针slow，初始时均指向首结点head。当fast不空且fast->next不空时，慢指针slow后移一个结点，快指针fast后移两个结点，若初始fast和slow指向同一个结点，则说明链表中有环，返回true。循环结束，即fast为空或者fast->next为空，说明链表中无环，返回false。

其基本原理相当于A和B两个人在一个环形跑道上从相同的起点出发跑步，A的速度正好是B的速度的两倍，则这两个人一定会再次相遇（相遇的位置与跑道的长度和跑步的速度有关），如图2.14所示。如果跑道是直线，不是环形，则速度快的人A一定会先冲出跑道（此时B正好在中间），如图2.15所示。

对应的算法如下。

C++：

提交运行：

Python：

提交运行：

2.2.6 LeetCode138——复制带随机指针的链表★★

【问题描述】 给定一个长度为 n 的链表head，每个结点包含一个额外增加的随机指针random，该指针可以指向链表中的任何结点或空结点，其结点类型Node如下，构造这个链表的深拷贝。

C++：

Python：

深拷贝应该正好由 n 个全新结点组成，其中每个新结点的值都设置为其对应原结点的值。新结点的next指针和random指针也都应该指向复制链表中的新结点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应该指向原链表中的结点。若原链表中有X和Y两个结点，其中X.random→Y，那么在复制链表中对应的两个结点x和y同样有x.random→y。返回复制链表的首结点。

例如，head为如图2.16所示的带随机指针的链表，4个结点的地址分别为a、b、c、d，复制后返回的链表为[[1，b，d]，[2，c，a]，[3，d，NULL]，[4，NULL，c]]。

【限制】 0≤ n ≤1000，-10 ⁴ ≤Node.val≤10 ⁴ ，Node.random为NULL或指向链表中的结点。

【解题思路】 两次遍历法 。以题目中的单链表head=[[1，b，d]，[2，c，a]，[3，d，NULL]，[4，NULL，c]]为例说明求解过程。

（1）为单链表head添加一个头结点h。

（2）遍历h，对于每个结点p（实际结点），复制一个val相同的结点q（复制结点），并且将结点q插在结点p之后，如图2.17（a）所示。

（3）再次遍历h，每个实际结点p对应的复制结点为p- next，前者random指向的结点为p- random，后者random指向的结点应该为p- random- next，为此执行p- next- random=p- random- next为复制结点设置正确的random值，如图2.17（b）所示。

（4）遍历h，删除所有复制结点，并且将它们依次链接起来构成复制单链表ans，如图2.17（c）所示。最后返回ans- next即可。

对应的算法如下。

C++：

提交运行：

Python：

提交运行：

2.2.7 LeetCode707——设计链表★★

【问题描述】 实现一个链表，每个结点存放一个整数val，整个链表存放整数序列（ a ₀ ， a ₁ ，…， a _{n -1} ），注意序号或者索引 i 从0开始，并且包含以下功能。

（1）geti（i）：获取链表中第 i 个结点的值。如果索引无效，则返回-1。

（2）addAtHead（val）：在链表的第一个元素之前添加一个值为val的结点，此时新结点将成为链表的第一个结点。

（3）addAtTail（val）：将值为val的结点添加到链表的最后一个结点之后。

（4）addAtIndex（i，val）：在链表中的第 i 个结点之前添加值为val的结点。如果 i 等于链表的长度，则该结点将添加到链表的末尾；如果 i 大于链表的长度，则不插入结点；如果 i 小于0，则在头部插入结点。

（5）deleteAtIndex（i）：如果索引 i 有效，则删除链表中的第 i 个结点。

【解法1】 用带头结点和长度成员的单链表实现链表 。题目没有规定必须用哪种形式的链表，从理论上讲，用单链表、双链表或者循环链表均可，链表可以带头结点，也可以不带头结点。解法1用带头结点的单链表head作为链表，链表的结点类型为Node，为了方便，在链表对象中增加数据成员length表示链表中结点的个数。例如，单链表（1，2，3）的示意图如图2.18所示。

设计私有成员函数geti（i），其功能是返回序号为 i 的结点的地址，与2.1.2节中geti（）算法的功能相同，在设计查找、插入和删除算法中均调用该算法。

【解法2】 用带尾结点和长度成员的循环单链表实现链表 。在解法1中，在链表尾插入val的算法（即addAtTail（int val））的时间复杂度为 O （ n ），如果改为用带尾结点指针rear的循环单链表作为链表，则该算法的时间复杂度降为 O （1），其他不变。例如，单链表（1，2，3）的示意图如图2.19所示。

同样设计私有成员函数geti（i），其功能是当满足0≤ i ≤ n -1时返回序号为 i 的结点的地址，在其他情况下返回空。 6ekGGRWhmnkF/eDLgQjyuCmNIQunnuvCsgDnjORg6thSqkv5qE9yUa5kOozaKy20