Go程序员面试算法宝典
上QQ阅读APP看书,第一时间看更新

1.12 如何展开链接列表

难度系数:★★★★☆

被考查系数:★★★☆☆

题目描述

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

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

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

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

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

分析与解答:

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

程序运行结果为