021 Merge Two Sorted Lists[E]

1 題目描述

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

難度：Easy

2 題目樣例

Example:Input: 1->2->4, 1->3->4Output: 1->1->2->3->4->4

3 題意分析

合併兩個有序的鏈表，並且返回合併後的新的有序鏈表。

可以說是數據結構題目中的簡單題目了。

但雖然是簡單題目，對於數據結構基礎的考察卻值得讓人好好反思一番。

（當年的數據結構渣十分痛心疾首的說道。）

（好吧，該反思的只有我。）

4 思路分析

1.遞歸法：

由於函數的返回值也是一個鏈表，所以我完全可以利用遞歸的思想，調用自身，直到兩個鏈表都為Null為止。

注意存在其中一個鏈表直接為空的情況。

代碼實現如下：

class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if(l1 == NULL) return l2; if(l2 == NULL) return l1; if(l1->val < l2->val) { l1->next = mergeTwoLists(l1->next, l2); return l1; } else { l2->next = mergeTwoLists(l2->next, l1); return l2; } }};

但是我們知道，遞歸的時間複雜度必定為一個很高的數量級。在代碼AC後，Detail里顯示出的信息也反映出這個方法在速度上確實不太靈光。

所以我們考慮不使用遞歸的方法。

2.直接比較法：

道理也很簡單，定義一個新的鏈表，比較作為函數參數的兩個鏈表，小的元素放進定義的新鏈表中，哪個小，就跳到哪個鏈表的下一個節點，與另一個鏈表的當前節點比較，重複上述過程。

因為給出的兩個鏈表本身是有序的，這給我們帶來了便利。

代碼實現如下：

class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if(l1 == NULL) return l2; if(l2 == NULL) return l1; ListNode* head = new ListNode(-1); ListNode *tmp = head; while(l1&&l2) { if (l1->val>l2->val) { tmp->next=l2; l2=l2->next; } else { tmp->next=l1; l1=l1->next; } tmp=tmp->next; } while(!l1&&l2) { tmp->next=l2; l2=l2->next; tmp=tmp->next; } while(!l2&&l1) { tmp->next=l1; l1=l1->next; tmp=tmp->next; } return head->next; } };

不過讓人很痛心的是，這種方法也沒有把程序優化多少......

5 後記

頂著窗外的煙花聲寫完了這篇題解...

祝各位讀者老爺除夕夜快樂！新的一年要笑口常開哦！

推薦閱讀：