這次來寫一下 LeetCode 的第 21 題，合併兩個有序鏈表。
題目描述
題目直接從 LeetCode 上截圖過來，題目如下：
上面的題就是 合併兩個有序鏈表 題目的截圖，同時 LeetCode 會根據選擇的語言給出了一個類的定義或者函數的定義，然後在其中實現 合併兩個有序鏈表 的解題過程。這次我使用 C 語言來進行完成。
C 語言給出的函數定義如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
}
通過函數定義可以看出，mergeTwoLists 函數的參數是兩個單向鏈表，然後返回值也是一個鏈表，我們要做的就是把兩個有序的鏈表合併成一個新的有序鏈表。
問題分析
這個題目中提供的兩個鏈表本身就是有序的鏈表，只要我們把鏈表的節點逐個的遍歷並比較一遍，就可以合併爲另外一個有序的列表。
我們來看一下下面的兩幅圖，當 鏈表 l1 節點上的值 和 鏈表 l2 節點上的值 進行比較時，只要 l1 節點上的值 小於等於 鏈表 l2 節點上的值 ，那麼我們就取 鏈表 l1 節點上的值 放入 新的鏈表節點 上，並將指向 鏈表 l1 節點的指針 移動到下一個元素 。 反之，則將 鏈表 l2 節點上的值 放入 新的鏈表節點 上，並將指向 鏈表 l2 節點的指針 移動到下一個元素。
在兩個有序鏈表節點個數相同的時候，這樣做是沒有問題的，如果兩個有序鏈表節點個數不相同的話，那麼當一個鏈表的所有節點已經遍歷完，那麼就去遍歷剩下的一條鏈表即可。如下圖。
代碼實現
C 語言的代碼如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
struct ListNode* ll1 = l1;
struct ListNode* ll2 = l2;
struct ListNode* ll = NULL;
struct ListNode* cur = NULL;
while (ll1 != NULL || ll2 != NULL) {
struct ListNode* tmp = (struct ListNode*)malloc(sizeof(struct ListNode));
tmp->next = NULL;
// 初始化新節點的指針
if (cur == NULL) {
cur = tmp;
ll = tmp;
} else { // 當前節點指針的下一個節點
cur->next = tmp;
cur = tmp;
}
// ll1爲NULL後，遍歷鏈表ll2
if (ll1 == NULL) {
tmp->val = ll2->val;
ll2 = ll2->next;
continue;
}
// ll2爲NULL後，遍歷鏈表ll1
if (ll2 == NULL) {
tmp->val = ll1->val;
ll1 = ll1->next;
continue;
}
// ll1節點的當前值小於等於ll2節點的當前值
// 則把ll1節點的當前值放入tmp節點中
if (ll1->val <= ll2->val) {
tmp->val = ll1->val;
ll1 = ll1->next;
} else {
tmp->val = ll2->val;
ll2 = ll2->next;
}
}
return ll;
}
代碼中有了詳細的註釋，就不對代碼做過多的解釋了。
提交結果
在寫完代碼後，點擊右下角的 “ 執行代碼 ”，然後觀察 “輸出” 和 “預期結果” 是否一致，一致的話就點擊 “ 提交 ” 按鈕。點擊 “提交” 按鈕後，系統會使用更多的測試用例來測試我們寫的函數體， 如果所有的測試用例都通過了，那麼就會給出 “通過” 的字樣， 如果沒有通過，會給出失敗的那一組測試用例，我們可以根據給出的測試用例來繼續修改代碼 。我們的代碼提交後的截圖如下：
喜歡就點在看哦~
