1.12 如何展開鏈接列表

難度系數：★★★★☆

被考查系數：★★★☆☆

題目描述：

給定一個有序鏈表，其中每個結點也表示一個有序鏈表，結點包含兩個類型的指針：

（1）指向主鏈表中下一個結點的指針（在下面的代碼中稱為“正確”指針）。

（2）指向此結點頭的鏈表（在下面的代碼中稱之為“down”指針）。

所有鏈表都被排序。請參見以下示例：

實現一個函數flatten()，該函數用來將鏈表扁平化成單個鏈表，扁平化的鏈表也應該被排序。例如，對于上述輸入鏈表，輸出鏈表應為3->6->8->11->15->21->22->30->31->39->40->45->50。

分析與解答：

本題的主要思路為使用歸并排序中的合并操作，使用歸并的方法把這些鏈表來逐個歸并。具體而言，可以使用遞歸的方法，遞歸地合并已經扁平化的鏈表與當前的鏈表。在實現的過程可以使用down指針來存儲扁平化處理后的鏈表。實現代碼如下：

程序運行結果為