4.4 反转链表
单向链表最大的特点就是其单向性，只能顺着指向下一个节点的指针方向从头到尾遍历链表而不能反方向遍历。这种特性用一句古诗来形容正合适：黄河之水天上来，奔流到海不复回。
有些面试题只有从链表尾节点开始遍历到头节点才容易解决。这个时候可以先将链表反转，然后在反转的链表中从头到尾遍历，这就相当于在原来的链表中从尾到头遍历。
下面介绍如何反转链表，以及如何利用反转链表来解决典型的算法面试题。
面试题24：反转链表
题目：定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。例如，把图4.8（a）中的链表反转之后得到的链表如图4.8（b）所示。
图4.8 反转一个链表
分析：首先确定函数的返回值。需要返回的是反转后链表的头节点。显然，反转之后链表的头节点是原始链表的尾节点，也就是说，原始链表中的next指针指向null的节点。
然后借助图形直观地分析如何通过调整链表中指针的方向来正确地反转链表。在如图4.9（a）所示的链表中，i、j和k是3个相邻的节点。假设经过若干次反转操作已经把节点i之前的指针都反转了，这些节点的next指针都指向前面一个节点。接下来把节点j的next指针指向节点i，此时的链表结构如图4.9（b）所示。
图4.9 反转链表节点中的next指针导致链表出现断裂
说明：（a）一个链表；（b）把节点j之前所有的节点的next指针都指向前一个节点，导致链表在节点j和k之间断裂
由于节点j的next指针指向了它的前一个节点i，因此链表在节点j和k之间断开，无法在链表中遍历到节点k。为了避免链表断开，需要在调整节点j的next指针之前把节点k保存下来。
也就是说，在调整节点j的next指针时，除了需要知道节点j本身，还需要知道节点j的前一个节点i，这是因为需要把节点j的next指针指向节点i。同时，还需要事先保存节点j的下一个节点k，以防止链表断开。因此，在遍历链表逐个反转每个节点的next指针时需要用到3个指针，分别指向当前遍历到的节点、它的前一个节点及后一个节点。
有了前面的分析，就可以编写出如下所示的代码来反转链表：
在上述代码中，变量cur指向当前遍历到的节点，变量prev指向当前节点的前一个节点，而变量next指向下一个节点。每遍历一个节点之后，都让变量prev指向该节点。在遍历到尾节点之后，变量prev最后一次被更新，因此，变量prev最终指向原始链表的尾节点，也就是反转链表的头节点。
显然，上述代码的时间复杂度是O（n），空间复杂度是O（1）。
面试题25：链表中的数字相加
题目：给定两个表示非负整数的单向链表，请问如何实现这两个整数的相加并且把它们的和仍然用单向链表表示？链表中的每个节点表示整数十进制的一位，并且头节点对应整数的最高位数而尾节点对应整数的个位数。例如，在图4.10（a）和图4.10（b）中，两个链表分别表示整数123和531，它们的和为654，对应的链表如图4.10（c）所示。
分析：这是一个看起来很简单的题目。很多应聘者的第一反应是根据链表求出整数，然后直接将两个整数相加，最后把结果用链表表示。这种思路的最大的问题是没有考虑到整数有可能会溢出。当链表较长时，表示的整数很大，可能会超出int甚至long的范围，如果根据链表求出整数就有可能会溢出。
由于示例中给出的两个链表的长度是一样的，因此很多应聘者没有经过细致思考就以为只要从两个链表的头节点开始逐个数位相加就可以。
图4.10 链表中的数字及它们的和
其实，只要分析一个长度不相同的两个链表相加的例子就能发现题目没有这么简单。例如，两个分别表示整数984和18的链表，它们相加时应该是984中的十位数8和18中的十位数1相加，984的个位数4和18的个位数8相加。此时不能从两个链表的头节点开始相加，而是应该把它们的尾节点对齐并把对应的数位相加。
通常，两个整数相加都是先加个位数，再加十位数，然后依次相加更高位数字。由于题目中的整数使用单向链表表示，因此先将两个尾节点相加，再将两个整数的倒数第2个节点相加，并依次对前面的节点相加。
但是两个尾节点相加之后，在单向链表中就无法前进到倒数第2个节点。在单向链表中只能从前面的节点朝着next指针方向前进到后面的节点，却无法从后面的节点前进到前面的节点。
解决这个问题的办法是把表示整数的链表反转。反转之后的链表的头节点表示个位数，尾节点表示最高位数。此时从两个链表的头节点开始相加，就相当于从整数的个位数开始相加。
在做加法时还需要注意的是进位。如果两个整数的个位数相加的和超过10，就会往十位数产生一个进位。在下一步做十位数相加时就要把这个进位考虑进去。
图4.11总结了用链表表示的两个整数984和18相加的过程。先把两个表示整数的链表反转，再在两个反转之后的链表中逐个节点实现加法，最后把表示和的链表反转。
图4.11 用链表表示的两个整数984和18相加的过程
说明：（a）把分别表示984和18的两个链表反转；（b）在反转之后的链表中从个位数开始相加；（c）把表示和的链表反转得到结果1002
该思路对应的代码如下所示：
函数reverseList和面试题24中的函数reverseList完全一样，这里就不再重复介绍。
面试题26：重排链表
问题：给定一个链表，链表中节点的顺序是L0→L1→L2→…→Ln-1→Ln，请问如何重排链表使节点的顺序变成L0→Ln→L1→Ln-1→L2→Ln-2→…？例如，输入图4.12（a）中的链表，重排之后的链表如图4.12（b）所示。
图4.12 重排链表
分析：如果仔细观察输入链表和输出链表之间的联系，就能发现重排链表其实包含以下几个操作。首先把链表分成前后两半。在示例链表中，前半段链表包含1、2、3这3个节点，后半段链表包含4、5、6这3个节点。然后把后半段链表反转。示例链表的后半段链表反转之后，节点的顺序变成6、5、4。最后从前半段链表和后半段链表的头节点开始，逐个把它们的节点连接起来形成一个新的链表。先把前半段链表和后半段链表的头节点1和6连接起来，再把处在第2个位置的节点2和5连接起来，最后把两个尾节点3和4连接起来，因此在新的链表中节点的顺序是1、6、2、5、3、4。
需要首先解决的问题是如何把一个链表分成两半。如果能够找到链表的中间节点，那么就能根据中间节点把链表分割成前后两半。位于中间节点之前的是链表的前半段，位于中间节点之后的是链表的后半段。
可以使用双节点来寻找链表的中间节点。如果一快一慢两个指针同时从链表的头节点出发，快的指针一次顺着next指针向前走两步，而慢的指针一次只走一步，那么当快的指针走到链表的尾节点时慢的指针刚好走到链表的中间节点。
一个值得注意的问题是，链表的节点总数既可能是奇数也可能是偶数。当链表的节点总数是奇数时，就要确保链表的前半段比后半段多一个节点。
在上述代码中，变量fast表示走得快的指针，一次走两步，变量slow表示走得慢的指针，一次只走一步。当变量fast指向尾节点时，变量slow指向前半段的最后一个节点。
变量slow指向的节点的下一个节点就是后半段的头节点，用变量temp表示。然后调用函数reverseList反转链表的后半段。该函数和前面几道面试题中的函数reverseList完全一样，这里就不再重复介绍。
面试题27：回文链表
问题：如何判断一个链表是不是回文？要求解法的时间复杂度是O（n），并且不得使用超过O（1）的辅助空间。如果一个链表是回文，那么链表的节点序列从前往后看和从后往前看是相同的。例如，图4.13中的链表的节点序列从前往后看和从后往前看都是1、2、3、3、2、1，因此这是一个回文链表。
图4.13 一个回文链表
分析：如果不考虑辅助空间的限制，直观的解法是创建一个新的链表，链表中节点的顺序和输入链表的节点顺序正好相反。如果新的链表和输入链表是相同的，那么输入链表就是一个回文链表。只是这种解法需要创建一个和输入链表长度相等的链表，因此需要O（n）的辅助空间。
仔细分析回文链表的特点以便找出更好的解法。回文链表的一个特性是对称性，也就是说，如果把链表分为前后两半，那么前半段链表反转之后与后半段链表是相同的。在如图4.13所示的包含6个节点的链表中，前半段链表的3个节点反转之后分别是3、2、1，后半段链表的3个节点也分别是3、2、1，因此它是一个回文链表。
如图4.13所示，链表的节点总数是偶数。如果链表的节点总数是奇数，那么把链表分成前后两半时不用包括中间节点。例如，一个链表中的节点顺序是1、2、k、2、1，前面两个节点反转之后是2、1，后面两个节点也是2、1，不管中间节点的值是什么该链表都是回文链表。
通过如此分析可知，这个题目的解法和面试题26的解法基本类似，都是尝试把链表分成前后两半，然后把其中一半反转。基于这种思路可以编写出如下所示的代码：
上述代码仍然是用一快一慢两个指针找出链表中的中间节点，并以此把链表分成前后两半。不管链表的节点总数是奇数还是偶数，变量slow都指向链表前半段的最后一个节点，变量secondHalf都指向链表后半段的第1个节点。如果链表的前半段反转之后和链表的后半段相同，那么它就是一个回文链表。
函数reverseList用来反转一个链表，由于该函数和前面几道面试题中的函数reverseList完全一样，因此这里就不再重复介绍。
通过解决这几道典型的面试题可以发现，反转链表是面试中经常出现的操作，所以能熟练、正确地编写出反转链表的代码非常重要。