4.5 双向链表和循环链表

由于单向链表只能从头节点开始遍历到尾节点，遍历的顺序受到限制，在很多场景下使用起来不是很方便，因此双向链表应运而生。双向链表在单向链表节点的基础上增加了指向前一个节点的指针，这样一来，既可以从头节点开始从前往后遍历到尾节点，也可以从尾节点开始从后往前遍历到头节点。

由于双向链表的每个节点多了一个指针，因此在双向链表中添加、删除节点等操作要稍微复杂一点。如果应聘者遇到双向链表的面试题，就要格外小心，确保节点的每个指针都指向了正确的位置。

如果把链表尾节点指向下一个节点的指针指向链表的头节点，那么此时链表就变成一个循环链表，相当于循环链表的所有节点都位于一个环中。循环链表既可以是单向链表也可以是双向链表。即使一个循环链表是单向链表，也可以从任意节点出发到达另一个任意节点，因此，在循环链表中任意节点都可以当作链表的头节点。

面试题28：展平多级双向链表

分析：在面试时如果遇到这种类型的题目，应聘者需要先弄清楚展平的规则。在图4.14的示例中，节点2有一个子链表，展平之后该子链表插入节点2和它的下一个节点3之间。节点6也有一个子链表，展平之后该子链表插入节点6和它的下一个节点7之间。由此可知，展平的规则是一个节点的子链展平之后将插入该节点和它的下一个节点之间。

由于子链表中的节点也可能有子链表，因此这里的链表是一个递归的结构。在展平子链表时，如果它也有自己的子链表，那么它嵌套的子链表也要一起展平。嵌套子链表和外层子链表的结构类似，可以用同样的方法展平，因此可以用递归函数来展平链表。递归代码如下所示：

在上述代码中，递归函数flattenGetTail在展平以head为头节点的链表之后返回链表的尾节点。在该函数中需要逐一扫描链表中的节点。如果一个节点node有子链表，由于子链表也可能有嵌套的子链表，因此先递归调用flattenGetTail函数展平子链表，子链表展平之后的头节点是child，尾节点是childTail。最后将展平的子链表插入节点node和它的下一个节点next之间，即把展平的子链表的头节点child插入节点node之后，并将尾节点childTail插入节点next之前。

这种解法每个节点都会遍历一次，如果链表总共有n个节点，那么时间复杂度是O（n）。函数flattenGetTail的递归调用次数取决于链表嵌套的层数，因此，如果链表的层数为k，那么该节点的空间复杂度是O（k）。

面试题29：排序的循环链表

分析：首先分析在排序的循环链表中插入节点的规律。当在图4.15（a）的链表中插入值为4的节点时，新的节点位于值为3的节点和值为5的节点之间。这很容易理解，为了使插入新节点的循环链表仍然是排序的，新节点的前一个节点的值应该比新节点的值小，后一个节点的值应该比新节点的值大。

但是特殊情况需要特殊处理。如果新节点的值比链表中已有的最大值还要大，那么新的节点将被插入最大值和最小值之间。例如，如果在图4.15（a）中插入值为7的节点，那么新节点位于原来值最大的节点和值最小的节点之间，如图4.16（a）所示。

新节点的值比链表中已有的最小值还要小的情形和前面类似，新的节点也将被插入最大值和最小值之间。例如，在图4.15（a）中插入值为0的节点，新节点也位于原来值最大的节点和值最小的节点之间，如图4.16（b）所示。

下面总结在排序的循环链表中插入新节点的规则。先试图在链表中找到相邻的两个节点，如果这两个节点的前一个节点的值比待插入的值小并且后一个节点的值比待插入的值大，那么就将新节点插入这两个节点之间。如果找不到符合条件的两个节点，即待插入的值大于链表中已有的最大值或小于已有的最小值，那么新的节点将被插入值最大的节点和值最小的节点之间。

在上面的规则中，总是先试图从链表中找到符合条件的相邻的两个节点。如果开始的时候链表中的节点数小于2，那么应该有两种可能。第1种可能是开始的时候链表是空的，一个节点都没有。此时插入一个新的节点，该节点成为循环链表中的唯一节点，那么next指针指向节点自己，如图4.17（a）所示。第2种可能是开始的时候链表中只有一个节点，插入一个新的节点之后，两个节点的next指针互相指向对方，如图4.17（b）所示。

将插入规则和各种边界条件都考虑清楚之后就可以开始编写代码。参考代码如下所示：

在函数insert中先处理链表是空的或链表中只有一个节点的情况，然后调用函数insertCore处理链表中的节点数超过一个的情况。在函数insertCore中试图找到相邻的两个节点cur和next，使cur的值小于或等于待插入的值且next的值大于或等于待插入的值。如果找到了就将新节点插入它们之间。如果没有找到符合条件的两个节点，就将新的节点插入值最大的节点biggest的后面。