第4章 链表
链表是最基本的数据结构，不仅在实际应用中有着非常重要的作用，而且也是程序员面试、笔试中必考的内容。具体而言，它的存储特点为：可以用任意一组存储单元来存储单链表中的数据元素（存储单元可以是不连续的），而且除了存储每个数据元素ai外，还必须存储指示其直接后继元素的信息。这两部分信息组成的数据元素ai的存储映像称为结点。N个结点链在一起被称为链表。如果结点只包含其后继结点的信息，这样的链表就被称为单链表，而链表的第一个结点通常被称为头结点。
单链表又可以将其分为有头结点的单链表和无头结点的单链表，如下图所示。
在单链表的开始结点之前附设一个类型相同的结点，称之为头结点，头结点的数据域可以不存储任何信息（也可以存放如线性表的长度等附加信息），头结点的指针域存储指向开始结点的指针（即第一个元素结点的存储位置）。
具体而言，头结点的作用主要有以下两点：
1）对于带头结点的链表，当在链表的任何结点之前插入新结点或删除链表中任何结点时，所要做的都是修改前一个结点的指针域，因为任何结点都有前驱结点。若链表没有头结点，则首元素结点没有前驱结点，在其前面插入结点或删除该结点时操作会复杂些，需要进行特殊的处理。
2）对于带头结点的链表，链表的头指针是指向头结点的非空指针，因此对空链表与非空链表的处理是一样的。
由于头结点有诸多的优点，因此本章中所介绍的算法都使用了带头结点的单链表。
如下是一个单链表数据结构的定义示例：
4.1 如何实现链表的逆序
难度系数：★★★☆☆
被考查系数：★★★★☆
题目描述：
给定一个带头结点的单链表，请将其逆序。即如果单链表原来为head→1→2→3→4→5→6→7，逆序后变为head→7→6→5→4→3→2→1。
分析与解答：
由于单链表分数组不同，单链表中每个结点的地址都存储在其前驱结点的指针域中，因此，对单链表中任意一个结点的访问只能从链表的头指针开始遍历。在对链表的操作过程中，需要特别注意在修改结点指针域的时候，记录下后继结点的地址，否则会丢失后继结点。
方法一：就地逆序法
假定原链表为1→2→3→4→5→6→7，就地逆序法的主要思路：先逆序除第一个结点以外的子链表（将1→2→3→4→5→6→7变为1→7→6→5→4→3→2），接着把结点1添加到逆序的子链表的后面（1→2→3→4→5→6→7变为7→6→5→4→3→2→1）。这个方法的缺点是改变了链表原来的结构。
如下是以单链表数据结构定义的就地逆序法示例：
程序的运行结果为
算法性能分析：
以上这种方法只需要对链表进行一次遍历，因此，时间复杂度为O（n）。其中，n 为链表的长度。但是需要常数个额外的变量来保存当前结点的前驱结点与后继结点，因此，空间复杂度为O（1）。
方法二：递归法
假定原链表为1→2→3→4→5→6→7，递归法的主要思路为：先逆序除第一个结点以外的子链表（将1→2→3→4→5→6→7变为1→7→6→5→4→3→2），接着把结点1添加到逆序的子链表的后面（1→2→3→4→5→6→7变为7→6→5→4→3→2→1）。同理，在逆序链表2→3→4→5→6→7时，也是先逆序子链表3→4→5→6→7（逆序为2→7→6→5→4→3），接着实现链表的整体逆序（2→7→6→5→4→3转换为7→6→5→4→3→2）。实现代码如下：
算法性能分析：
递归法也只需要对链表进行一次遍历，因此，算法复杂度也为O（n）。其中，n 为链表的长度。递归法的主要优点是：算法的思路比较直观，容易理解，而且也不需要保存前驱结点的地址；缺点是：算法实现的难度较大。此外，由于递归法需要不断地调用自己，需要额外的压栈与弹栈操作，因此，与方法一相比性能会有所下降。
方法三：插入法
插入法的主要思路：从链表的第二个结点开始，把遍历到的结点插入到头结点的后面，直到遍历结束。假定原链表为head→1→2→3→4→5→6→7，在遍历到2时，将其插入到头结点后，链表变为head→2→1→3→4→5→6→7，同理将后序遍历到的所有结点都插入到头结点head后，就可以实现链表的逆序。实现代码如下：
算法性能分析：
以上这种方法也只需要对单链表进行一次遍历，因此，时间复杂度为O（n）。其中，n 为链表的长度。与方法一相比，这种方法不需要保存前驱结点的地址，与方法二相比，这种方法不需要递归的调用，效率更高。
4.2 如何从无序链表中移除重复项
难度系数：★★★☆☆
被考查系数：★★★★☆
题目描述：
给定一个没有排序的链表，去掉其重复项，并保留原顺序，如链表1→3→1→5→5→7，去掉重复项后变为1→3→5→7。
分析与解答：
方法一：顺序删除
主要思路为：通过双重循环直接在链表上执行删除操作。外层循环用一个指针从第一个结点开始遍历整个链表，然后内层循环用另外一个指针遍历其余结点，将与外层循环遍历到的指针所指结点的数据域相同的结点删除。如下图所示。
假设外层循环从outerCur 开始遍历，当内层循环指针innerCur 遍历到上图虚线所框的位置（outerCur→data=innerCur→data）时，此时需要把innerCur指向的结点删除。具体步骤如下：
1）用tmp记录待删除的结点的地址。
2）为了能够在删除tmp结点后继续遍历链表中其余的结点，使innerCur指针指向它的后继结点：innerCur=innerCur→next。
3）从链表中删除tmp结点。
4）释放tmp结点所占的内存空间。
实现代码如下：
程序的运行结果为
算法性能分析：
由于这个算法采用双重循环对链表进行遍历，因此，时间复杂度为O（n2）。其中，n为链表的长度。在遍历链表的过程中，使用了常量个额外的指针变量来保存当前遍历的结点、前驱结点和被删除的结点，因此，空间复杂度为O（1）。
方法二：递归法
主要思路为：对于结点cur，首先递归地删除以cur→next为首的子链表中重复的结点，接着从以cur→next为首的子链表中找出与cur有着相同数据域的结点并删除。实现代码如下：
使用这个方法可以得到相同运行结果。
算法性能分析：
这个方法与方法一类似，从本质上而言，由于这个方法需要对链表进行双重遍历，因此，时间复杂度为O（n2）。其中，n为链表的长度。由于递归法会增加许多额外的函数调用，因此，从理论上讲，该方法效率比方法一低。
方法三：空间换时间
通常情况下，为了降低时间复杂度，往往在条件允许的情况下，通过使用辅助空间实现。具体而言，主要思路如下。
1）建立一个数组，数组中的内容为已经遍历过的结点内容，并将其初始化为空。
2）从头开始遍历链表中的所有结点，存在以下两种可能性：
① 如果结点内容已经在数组中，则删除此结点，继续向后遍历。
② 如果结点内容不在数组中，则保留此结点，将此结点内容添加到数组中，继续向后遍历。
引申：如何从有序链表中移除重复项。
分析与解答：
上述介绍的方法也适用于链表有序的情况，但是由于以上方法没有充分利用到链表有序这个条件，因此，算法的性能肯定不是最优的。本题中，由于链表具有有序性，因此，不需要对链表进行两次遍历。所以，有如下思路：用cur 指向链表第一个结点，此时需要分为以下两种情况讨论。
1）如果cur→data=cur→next→data，那么删除cur→next结点。
2）如果cur→data!=cur→next→data，那么cur=cur→next，继续遍历其余结点。
实现代码如下：
4.3 如何计算两个单链表所代表的数之和
难度系数：★★★☆☆
被考查系数：★★★★☆
题目描述：
给定两个单链表，链表的每个结点代表一位数，计算两个数的和。例如，输入链表（3→1→5）和链表（5→9→2），输出：8→0→8，即513+295=808，注意个位数在链表头。
分析与解答：
方法一：整数相加法
主要思路为：分别遍历两个链表，求出两个链表所代表的整数的值，然后把这两个整数进行相加，最后把它们的和用链表的形式表示出来。这种方法的优点是计算简单。
方法二：链表相加法
主要思路为：对链表中的结点直接进行相加操作，把相加的和存储到新的链表中对应的结点中，同时还要记录结点相加后的进位。如下图所示。
使用这个方法需要注意如下几个问题：①每组结点进行相加后需要记录其是否有进位；②如果两个链表h1与h2的长度不同（长度分别为L1和L2，且L1＜L2），当对链表的第L1位计算完成后，接下来只需要考虑链表h2剩余的结点的值（需要考虑进位）；③对链表所有结点都完成计算后，还需要考虑此时是否还有进位，如果有进位，则需要增加新的结点，此结点的数据域为1。实现代码如下：
程序的运行结果为
运行结果分析：
前5位可以按照整数相加的方法依次从左到右进行计算，第5位7+5+1（进位）的值为3，进位为1。此时，Head2已经遍历结束，由于Head1还有结点没有被遍历，所以，依次接着遍历Head1剩余的结点：8+1（进位）=9，没有进位。因此，运行代码可以得到上述结果。
算法性能分析：
由于这个方法需要对两个链表都进行遍历，因此，时间复杂度为O（n），其中，n 为较长的链表的长度，由于计算结果保存在一个新的链表中，因此，空间复杂度也为O（n）。
4.4 如何对链表进行重新排序
难度系数：★★★☆☆
被考查系数：★★★★☆
题目描述：
给定链表L0→L1→L2→…→Ln-1→Ln，把链表重新排序为L0→Ln→L1→Ln-1→L2→Ln-2→…。要求：①在原来链表的基础上进行排序，即不能申请新的结点；②只能修改结点的next域，不能修改数据域。
分析与解答：
主要思路为：
1）首先找到链表的中间结点。
2）对链表的后半部分子链表进行逆序。
3）把链表的前半部分子链表与逆序后的后半部分子链表进行合并，合并的思路为：分别从两个链表各取一个结点进行合并。实现方法如下图所示（以自然数数组1～7为例）。
实现代码如下：
程序的运行结果为
算法性能分析：
查找链表的中间结点的方法的时间复杂度为O（n），逆序子链表的时间复杂度也为O（n），合并两个子链表的时间复杂度也为O（n）。因此，整个方法的时间复杂度为O（n），其中，n表示的是链表的长度。由于这个方法只用了常数个额外指针变量，因此，空间复杂度为O（1）。
引申：如何查找链表的中间结点。
分析与解答：
主要思路为：用两个指针从链表的第一个结点开始同时遍历结点，一个快指针每次走两步，另外一个慢指针每次走一步；当快指针先到链表尾部时，慢指针则恰好到达链表中部。快指针到链表尾部时，如果链表长度为奇数，那么慢指针指向的即是链表中间指针；如果链表长度为偶数，那么慢指针指向的结点和该结点的下一个结点都是链表的中间结点。在上面的代码中，FindMiddleNode（）就是用来求取链表中间结点的方法。
4.5 如何找出单链表中的倒数第k个元素
难度系数：★★★☆☆
被考查系数：★★★★★
题目描述：
找出单链表中的倒数第k个元素，如给定单链表：1→2→3→4→5→6→7，则单链表的倒数第3（即k=3）个元素为5。
分析与解答：
方法一：顺序遍历两遍法
主要思路为：首先遍历一遍单链表，求出整个单链表的长度n，然后把求倒数第k 个元素转换为求顺数第n-k个元素，再去遍历一次单链表就可以得到结果。但是该方法需要对单链表进行两次遍历。
方法二：快慢指针法
由于单链表只能从头到尾依次访问链表的各个结点，所以，如果要找单链表的倒数第k个元素，也只能从头到尾进行遍历查找。在查找过程中，设置两个指针，让其中一个指针比另外一个指针先前移k步，然后两个指针同时往前移动。循环直到先行的指针值为NULL时，另外一个指针所指的位置就是所要找的位置。实现代码如下。
程序的运行结果为
算法性能分析：
这种方法只需要对链表进行一次遍历，因此，时间复杂度为O（n）。另外，由于只需要常量个指针变量来保存结点的地址信息，因此，空间复杂度为O（1）。
引申：如何将单链表向右旋转k个位置。
题目描述：给定单链表1→2→3→4→5→6→7，k=3，那么旋转后的单链表变为5→6→7→1→2→3→4。
分析与解答：
主要思路为：①首先找到链表倒数第k+1个结点slow和尾结点fast（如下图所示）；②把链表断开为两个子链表，其中后半部分子链表结点的个数为k；③使原链表的尾结点指向链表的第一个结点；④使链表的头结点指向原链表倒数第k个结点。
实现代码如下：
程序的运行结果为
算法性能分析：
这种方法只需要对链表进行一次遍历，因此，时间复杂度为O（n）。另外由于只需要几个指针变量来保存结点的地址信息，因此，空间复杂度为O（1）。
4.6 如何检测一个较大的单链表是否有环
难度系数：★★★★☆
被考查系数：★★★★★
题目描述：
单链表有环指的是单链表中某个结点的next指针域指向链表中在它之前的某一个结点，这样在链表的尾部形成一个环形结构。如何判断单链表是否有环存在？
分析与解答：
方法：快慢指针遍历法
定义两个指针fast（快）与slow（慢），两者的初始值都指向链表头，指针slow每次前进一步，指针fast 每次前进两步。两个指针同时向前移动，快指针每移动一次都要跟慢指针比较，如果快指针等于慢指针，就证明这个链表是带环的单向链表，否则证明这个链表是不带环的循环链表。实现代码见下面引申部分。
引申：如果链表存在环，那么如何找出环的入口点。
分析与解答：
当链表有环时，如果知道环的入口点，那么在需要遍历链表或释放链表所占的空间时方法将会非常简单，下面主要介绍查找链表环入口点的思路。
如果单链表有环，那么按照上述方法二的思路，当走得快的指针fast与走得慢的指针slow相遇时，slow指针肯定没有遍历完链表，而fast指针已经在环内循环了n圈（n≥1）。如果slow指针走了s步，则fast指针走了2s步（fast步数还等于s 加上在环上多转的n圈），假设环长为r，则满足如下关系表达式：
2s=s+nr
由此可以得到：s=nr
设整个链表长为L，入口环与相遇点距离为x，起点到环入口点的距离为a。则满足如下关系表达式：
a+x=nr
a+x=（n-1）r+r=（n-1）r+L-a
a=（n-1）r+（L-a-x）
（L-a-x）为相遇点到环入口点的距离，从链表头到环入口点的距离=（n-1）×环长+相遇点到环入口点的长度，于是从链表头与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。实现代码如下：
程序的运行结果为
运行结果分析：
示例代码中给出的链表为1→2→3→4→5→6→7→3（3实际代表链表第三个结点）。因此， IsLoop函数返回的结果为两个指针相遇的结点，所以链表有环，通过函数FindLoopNode可以获取到环的入口点为3。
算法性能分析：
这种方法只需要对链表进行一次遍历，因此，时间复杂度为O（n）。另外，由于只需要几个指针变量来保存结点的地址信息，因此，空间复杂度为O（1）。
4.7 如何把链表相邻元素翻转
难度系数：★★★☆☆
被考查系数：★★★★☆
题目描述：
把链表相邻元素翻转，如给定链表为1→2→3→4→5→6→7，则翻转后的链表变为2→1→4→3→6→5→7。
分析与解答：
方法一：交换值法
最容易想到的方法就是交换相邻两个结点的数据域，这种方法由于不需要重新调整链表的结构，因此比较容易实现，但是这种方法并不是考官所期望的解法。
方法二：就地逆序
主要思路为：通过调整结点指针域的指向来直接调换相邻的两个结点。如果单链表恰好有偶数个结点，那么只需要将奇偶结点对调，如果链表有奇数个结点，那么除最后一结点外的其他结点进行奇偶对调。为了便于理解，下图给出了其中第一对结点对调的方法。
在上图中，当前遍历到结点cur，通过步骤（1）～（6）用虚线的指针来代替实线的指针实现相邻结点的逆序。其中，步骤（1）～（4）实现了前两个结点的逆序操作，步骤（5）和（6）向后移动指针，接着可以采用同样的方式实现后面两个相邻结点的逆序操作。实现代码如下：
程序的运行结果为
上例中，由于链表有奇数个结点，因此，链表前三对结点相互交换，而最后一个结点保持在原来的位置。
算法性能分析：
这种方法只需要对链表进行一次遍历，因此，时间复杂度为O（n）。另外，由于只需要几个指针变量来保存结点的地址信息，因此，空间复杂度为O（1）。
4.8 如何把链表以K个结点为一组进行翻转
难度系数：★★★☆☆
被考查系数：★★★★☆
题目描述：
K链表翻转是指把每K个相邻的结点看成一组进行翻转，如果剩余结点不足K个，则保持不变。假设给定链表1→2→3→4→5→6→7和一个数K，如果K的值为2，那么翻转后的链表为2→1→4→3→6→5→7。如果K的值为3，那么翻转后的链表为：3→2→1→6→5→4→7。
分析与解答：
主要思路为：首先把前K个结点看成一个子链表，采用前面介绍的方法进行翻转，把翻转后的子链表链接到头结点后面，然后把接下来的K个结点看成另外一个单独的链表进行翻转，把翻转后的子链表链接到上一个已经完成翻转子链表的后面。具体实现方法如下图所示。
在上图中，以K=3为例介绍具体实现的方法：
1）首先设置pre指针指向头结点，然后让指针begin指向链表第一个结点，找到从begin开始第3（即K=3）个结点end。
2）为了采用4.1节中链表翻转的算法，需要使end-＞next=NULL，在此之前需要记录下end指向的结点（end-＞next），用指针pNext来记录。
3）使end-＞next=NULL，使得从begin到end为一个单独的子链表，从而可以对这个子链表采用4.1节介绍的方法进行翻转。
4）对以begin为第一个结点，end为尾结点所对应的K=3个结点进行翻转。
5）由于翻转后子链表的第一个结点从begin变为end，因此，执行pre-＞next=end，把翻转后的子链表链接起来。
6）把链表中剩余的还未完成翻转的子链表链接到已完成翻转的子链表后面。
7）让pre指针指向已完成翻转的链表的最后一个结点。
8）让begin指针指向下一个需要被翻转的子链表的第一个结点（通过begin=pNext来实现）。
接下来可以反复使用步骤（1）～（8）对链表进行翻转。
实现代码如下：
程序的运行结果为
运行结果分析：
由于K=3，因此，链表可以分成三组（1 2 3）、（4 5 6）、（7）。对（1 2 3）翻转后变为（3 2 1），对（4 5 6）翻转后变为（6 5 4）。由于（7）这个子链表只有一个结点（小于3个），因此不进行翻转，所以翻转后的链表就变为3→2→1→6→5→4→7。
算法性能分析：
这种方法只需要对链表进行一次遍历，因此，时间复杂度为O（n）。另外，由于只需要几个指针变量来保存结点的地址信息，因此，空间复杂度为O（1）。
4.9 如何合并两个有序链表
难度系数：★★★☆☆
被考查系数：★★★★☆
题目描述：
已知两个链表head1和head2各自有序（如升序排列），请把它们合并成一个链表，要求合并后的链表依然有序。
分析与解答：
分别用指针head1、head2来遍历两个链表，如果当前head1指向的数据小于head2指向的数据，则将head1指向的结点归入合并后的链表中，否则将head2指向的结点归入合并后的链表中。如果有一个链表遍历结束，则把未结束的链表连接到合并后的链表尾部。
下图以一个简单的示例介绍合并的具体方法。
由于链表按升序排列，首先通过比较链表第一个结点中元素的大小来确定最终合并后链表的头结点；接下来每次都找两个链表中剩余结点的最小值链接到被合并的链表后面，如上图中的虚线所示。在实现的时候需要注意，要释放head2链表的头结点，实现代码如下：
程序的运行结果为
算法性能分析：
这种方法只需要对链表进行一次遍历，因此，时间复杂度为O（n）。另外，由于只需要几个指针变量来保存结点的地址信息，因此，空间复杂度为O（1）。