1.9 如何合并兩個有序鏈表

【出自ALBB筆試題】

難度系數：★★★☆☆

被考察系數：★★★★☆

題目描述：

已知兩個鏈表head1 和head2 各自有序（如升序排列），請把它們合并成一個鏈表，要求合并后的鏈表依然有序。

分析與解答：

分別用指針head1、head2來遍歷兩個鏈表，如果當前head1指向的數據小于head2指向的數據，則將head1 指向的結點歸入合并后的鏈表中，否則將head2 指向的結點歸入合并后的鏈表中。如果有一個鏈表遍歷結束，則把未結束的鏈表連接到合并后的鏈表尾部。

下圖以一個簡單的示例為例介紹合并的具體方法。

由于鏈表按升序排列，首先通過比較鏈表第一個結點中元素的大小來確定最終合并后鏈表的頭結點；接下來每次都找兩個鏈表中剩余結點的最小值鏈接到被合并的鏈表后面，如上圖中的虛線所示。在實現的時候需要注意，要釋放head2鏈表的頭結點，實現代碼如下：

程序的運行結果為

算法性能分析：

以上這種方法只需要對鏈表進行一次遍歷，因此，時間復雜度為O（n）。另外，由于只需要幾個指針變量來保存結點的地址信息，因此，空間復雜度為O（1）。