1.12 如何展开链接列表

难度系数：★★★★☆

被考查系数：★★★☆☆

题目描述：

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

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

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

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

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

分析与解答：

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

程序运行结果为