1.12 如何展开链接列表

【出自TX面试题】

难度系数：★★★★☆

被考察系数：★★★☆☆

题目描述：

给定一个有序链表，其中每个结点也表示一个有序链表，结点包含两个类型的指针：

1）指向主链表中下一个结点的指针（在下面的代码中称为“正确”指针）。

2）指向此结点头的链表（在下面的代码中称之为“down”指针）。

所有链表都被排序。参见以下示例：

实现一个函数flatten（），该函数用来将链表扁平化成单个链表，扁平化的链表也应该被排序。例如，对于上述输入链表，输出链表应为3→6→8→11→15→21→22→30→31→39→40→45→50。

分析与解答：

本题的主要思路为：使用归并排序中的合并操作，使用归并的方法把这些链表来逐个归并。具体而言，可以使用递归的方法，递归地合并已经扁平化的链表与当前的链表。在实现的过程可以使用down指针来存储扁平化处理后的链表。实现代码如下：

程序运行结果为