反转链表
该问题是“给定链表(表头节点)，将链表逆序，要求原地完成(由原节点构成)且只占常数额外空间”。先考虑递归程序，思路是递归进入到链表尾，然后在每次递归退出时，让外层递归把当前节点原后继的\(next\)反过来指向当前节点。需注意最后一次递归结束后，其当前节点的\(next\)没有发生变化，所以要特别的将其指向空，那为了方便干脆在每轮递归结束前都加一步把当前节点的\(next\)指向空。然后是如何记录新表头，上述递归没有用到函数返回值，可以一层层返回新表头。
1 2 3 4 5 6 7 | def f(node): if not node.next: return node newHead = f(node.next) node.next.next = node node.next = None return newHead |
然后考虑只遍历一次的非递归程序，如上图所示，先把链表分为“已反转子链表\(L_1\)”和“未反转子链表\(L_2\)”，并要求每次迭代后，\(L_1,L_2\)的每个节点的\(next\)都符合已反转子链表、未反转子链表的意义的。表示\(L_1,L_2\)表头的变量\(h_1,h_2\)在每次迭代后都是符合定义的。迭代开始前\(h_1\)为空，\(h2_2\)为原链表表头。然后执行如下迭代步骤：
1) 建立临时变量\(tmp\)指向\(h_2.next\)。\(tmp\)即将作为新\(h_2\)；
2) 将\(h_2.next\)指向\(h_1\)。\(h_2\)即将作为新\(h_1\)；
3) 把\(h_1\)指向\(h_2\)，再把\(h_2\)指向\(tmp\)。当前迭代的工作已做完，这步是为下轮迭代提供正确的\(h_1,h_2\)；
4) 当前\(h_2\)为空则程序结束，当前\(h_1\)就是新的表头，否则继续返回(1)迭代；
1 2 3 4 5 6 7 8 9 | def f(head): h1 = None h2 = head while True: tmp = h2.next h2.next = h1 h1, h2 = h2, tmp if not tmp: return h1 |
逆序存储链表
该问题是“给定链表(表头)，将其按遍历逆序存入数组”。该问题很简单，如果用递归遍历，就不用反转链表或数组。
1 2 3 4 5 6 7 8 9 10 11 | def f(head): result = [] def r(head): if head: r(head.next) result.append(head) r(head) return result |
按大小划分链表
该问题是“给定链表和\(x\)，使所有小于\(x\)的节点在不小于\(x\)的节点前，且两部分链表节点各保持原有顺序，要求原地完成(由原节点构成)且只占常数额外空间”。这个问题就是稳定的快速排序算法在每次迭代时要解决的问题。这里的思路是想办法按小于\(x\)和大于等于\(x\)分割成2个链表，再把两个链表接起来。具体就是先遍历原链表\(L_1\)，遇到小于\(x\)的元素不操作，遇到大于等于\(x\)的元素就将其从\(L_1\)取下接到\(L_2\)尾部。遍历结束后再将\(L_1\)表尾指向\(L_2\)表头即可。
这个问题的逻辑本身简单，但用程序实现时要考虑的边界比较多，这也是链表类问题的特点。比如删\(L_1\)元素的迭代过程要记录待删除节点的前驱才能实现，且还要考虑到表头被删的情况。对于\(L_2\)则要记得把最终表尾的\(next\)指向空，且还要考虑到初始时\(L_2\)是空的。为了处理这些情况，可以在原表头前加一个自己创建的节点作为新表头，最后记得还原回去即可。这样的好处是“删除表头”、“表头为空”等情况好处理，都可借助自己创建的节点的\(next\)完成。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | def f(head, x): h1 = n1 = ListNode(0) h2 = n2 = ListNode(0) h1.next = head while n1.next: if n1.next.val < x: n1 = n1.next else: n2.next = n1.next n1.next = n1.next.next n2 = n2.next n2.next = None n1.next = h2.next return h1.next |
合并排序链表
该问题是“给定\(A,B\)两个升序链表(表头)，将其合并为一个，要求原地完成(用原来的节点)且只占常数的额外空间”。先创建存储结果的空链表\(L\)，使用上面提到的技巧，先自己创建一个节点作为其表头。然后跟合并排序数组的思路一样，每轮比较\(A,B\)最左端两个数，取下其中最小的节点追加到\(L\)尾部，直到有一个链表为空，把另一个链表追加到\(L\)的尾部即可。最后\(L\)的表头(自己创建的节点的后继节点)就是结果链表的表头。具体实现如下。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | def f(l1, l2): h = ListNode(0) hh = h while l1 and l2: if l1.val < l2.val: h.next = l1 l1 = l1.next else: h.next = l2 l2 = l2.next h = h.next h.next = None if not l2: h.next = l1 return hh.next if not l1: h.next = l2 return hh.next |
链表加法
该问题是“给定\(A,B\)链表(表头)，两个链表分别表示两个整数，其中链表元素是0~9的1位十进制数，链表元素的次序表示从低位到高位，比如3=>2=>1表示123。要求输出同样格式的链表能表示上述两数之和”。这个问题的关键点是进位以及进位导致的边界情况的处理，由于每次的位相加最大只能得到9+9+进位=19，所以只需一个额外变量描述上次是否进位即可。当\(A,B\)都遍历完时，仍有可能还有1个之前的进位，需要为其再创建一个节点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | def f(h1, h2): hh = h = ListNode(None) flg = False while flg or h1 or h2: v = 1 if flg else 0 if h1: v += h1.val h1 = h1.next if h2: v += h2.val h2 = h2.next if v >= 10: v -= 10 flg = True else: flg = False h.next = ListNode(v) h = h.next return hh.next |
两两交换链表节点
该问题是“给定链表(表头)，从左到右两两交换节点位置，剩一个元素时无需交换。比如1-2-3-4-5变为2-1-4-3-5”。这个问题的关键是区分边界，因为表头会改变，所以这里先创建一个节点\(N\)，把原表头接到其后面。想要实现交换2个节点的位置，那这2个节点必须要能表示成“后继”和“后继的后继”。这里给出具体迭代步骤：
1) 初始化\(h = N\)；
2) 若\(h.next\)或\(h.next.next\)不存在，则\(h\)之后的部分无需再交换，程序结束返回\(N.next\)；
3) 交换\(h.next, h.next.next\)的位置并维护相关指针的正确性；
4) \(h = h.next.next\)然后返回步骤(2)；
上述步骤中每一轮都是利用\(x\)来交换\(x.next,x.next.next\)，一轮结束后\(x\)前进两步，就又能交换后面另外两个节点，当某一轮的\(x\)发现后不到2个节点时，就说明无需继续交换，程序退出。
1 2 3 4 5 6 7 8 9 10 | def f(head): hh = h = ListNode(None) h.next = head while h.next and h.next.next: tmp = h.next h.next = tmp.next tmp.next = h.next.next h.next.next = tmp h = h.next.next return hh.next |
奇偶链表
该问题是“给定链表(表头)，其节点是从1开始编号的，整理链表使奇数编号节点都在偶数编号节点前，并维持原顺序。要求原地完成(用原来的节点)并只占常数额外空间，比如输入a-b-c-d-e输出a-c-e-b-d”。这个问题的解决框架和上述“两两交换链表节点”类似，每次迭代都以“当前节点、当前节点后继、当前节点后继的后继”3个为一组操作，每次都把奇数节点取下接入“奇数链表”，最后当前链表会是“偶数链表”，合并两链表即可。程序实现如下，这里还是用创建表头的技巧处理边界。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | def f(head): h1 = hh1 = ListNode(None) h2 = hh2 = ListNode(None) h1.next = head while h1.next: tmp = h1.next h1.next = h1.next.next if h1.next: h1 = h1.next h2.next = tmp h2 = h2.next h2.next = None h2.next = hh1.next return hh2.next |
倒数第\(n\)个链表节点
该问题是“给定链表(表头)，求其倒数第\(n\)个节点(从1开始计数)”。这个问题容易想到的方法是先遍历一次求出节点数，换算出其正序编号，然后遍历第二次找到这个节点。这里看一种只遍历一次的方法，首先设两个变量\(x,y\)指向表头，然后开始迭代，每次迭代结束做\(x = x.next\)。当第\(n\)次迭代结束时后，之后每次迭代结束还要额外做\(y = y.next\)。最终当\(x\)到达表尾程序结束时，\(y\)指向的就是倒数第\(n\)个节点。由于用了2个变量(指针)，所以这种方法也叫“双指针法”。具体实现如下。
1 2 3 4 5 6 7 8 9 | def f(node, n): i = 0 x = y = node while x: i += 1 x = x.next if i > n: y = y.next return y |
排序链表的中位数
该问题是“给定升序排序的链表(表头)，求其中位数节点，当节点数为偶数，则返回中间两个节点靠左的”。这里使用另一种基于2个指针的策略，称为“快慢指针法”。同样是先用两个变量\(x,y\)指向表头，然后开始迭代，每轮\(x\)前进1个节点，\(y\)前进2个节点。当\(y\)到达链表尾时，\(x\)就停在中位数节点上。实现时要处理好\(y\)前进2次导致的边界情况，具体步骤如下：
1) 初始时\(x,y\)都指向表头；
2) \(y\)前进一步，如果失败(\(y.next\)指向空)则程序结束返回\(x\)；
3) \(y\)前进一步，如果失败(\(y.next\)指向空)则程序结束返回\(x\)；
4) \(x\)前进一步，然后回到(2)。如果能到达这一步，那这一步不可能失败；
只要链表有至少1个节点，该步骤就能找到题意的节点。节点数为奇数时程序在(2)结束，偶数时在(3)结束。
1 2 3 4 5 6 7 8 9 10 | def f(node): x = y = node while True: if not y.next: return x y = y.next if not y.next: return x y = y.next x = x.next |
判断链表环
该问题是“给定链表(表头)，其允许节点的\(next\)指向比其遍历序更前的节点，这时会形成环路，请判断该链表是否有环”。容易想到的方法是遍历时用额外数组记录已访问节点，每次遍历都去这个数组中检查，其代价是\(O(n^2)\)并占用\(O(n)\)的额外空间，这其实就是深度优先搜索。这里用“快慢指针法”实现更优的程序，先看上面“排序链表的中位数”程序，如果某轮迭代退出则直接说明链表无环，有环的话迭代永远不会结束。如果一轮迭代没退出，那么\(y\)前进2次，\(x\)前进1次，所以当有环时，无论环多大，一定在某轮迭代结束时\(x,y\)指向相同元素，那么在每轮迭代结束时加一步检查\(x,y\)，相同则判定有环并返回。
简单讨论下时间复杂度，首先可以确定\(x\)在环上至多绕一圈，因为\(x\)如果在环上，\(y\)必然也在环上，如果\(x\)绕了一圈程序还未退出，那么\(y\)就绕了2圈，\(y\)一定会在某个节点与\(x\)相遇。这说明\(x\)至多走\(O(n)\)步，程序整体代价为\(O(n)\)。
1 2 3 4 5 6 7 8 9 10 11 12 | def f(node): x = y = node while True: if not y.next: return False y = y.next if not y.next: return False y = y.next x = x.next if x is y: return True |
链表环的入口
该问题是“给定链表(表头)，判断其是否有环并找到环入口(顺序遍历时最先到达的环节点)”。这里以上面的“判断链表环”的程序为基础来讨论，设从表头出发走\(s\geq 0\)步能到环入口，从环入口出发走\(k\geq 1\)步能到其自身(也是环节点数)。
为讨论\(s\)与\(k\)的倍数的关系，将\(s\)表示为\(s = nk + m\)，\(0\leq m<k\)与\(n\geq 0\)为整数。当\(x\)走到环入口时\(y\)多走\(nk+m\)步，\(y\)的当前位置可看作其从环入口出发走了\(m\)步，此时\(y\)继续走\(k-m\)步可达\(x\)，但在程序里\(y\)是跟着\(x\)走的，那就让\(x\)走\(k-m\)步，\(y\)会多走\(k-m\)步刚好能追上\(x\)相遇，这说明从相遇点出发走\(m\)步可到达环入口，根据\(s = nk + m\)，这意味着相遇后，从相遇点和表头出发2个指针，每次都只走1步，经过\(nk + m\)步两指针会在环入口相遇。由于\(nk + m\)是未知的，在程序中两个指针每走一次就互相看一下是否相等即可。具体程序如下，这里直接使用一部分上面的函数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | def meetAt(node): x = y = node while True: if not y.next: return False y = y.next if not y.next: return False y = y.next x = x.next if x is y: return x def f(head): node = meetAt(head) if node: while head != node: head = head.next node = node.next return head |