- Go程序员面试算法宝典
- 猿媛之家组编 董良松 楚秦等编著
- 332字
- 2020-06-25 22:38:08
1.12 如何展开链接列表
难度系数:★★★★☆
被考查系数:★★★☆☆
题目描述:
给定一个有序链表,其中每个结点也表示一个有序链表,结点包含两个类型的指针:
(1)指向主链表中下一个结点的指针(在下面的代码中称为“正确”指针)。
(2)指向此结点头的链表(在下面的代码中称之为“down”指针)。
所有链表都被排序。请参见以下示例:

实现一个函数flatten(),该函数用来将链表扁平化成单个链表,扁平化的链表也应该被排序。例如,对于上述输入链表,输出链表应为3->6->8->11->15->21->22->30->31->39->40->45->50。
分析与解答:
本题的主要思路为使用归并排序中的合并操作,使用归并的方法把这些链表来逐个归并。具体而言,可以使用递归的方法,递归地合并已经扁平化的链表与当前的链表。在实现的过程可以使用down指针来存储扁平化处理后的链表。实现代码如下:



程序运行结果为
