將兩個升序鏈表合并為一個新的 升序 鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的。

示例 1：

輸入：l1 = [1,2,4], l2 = [1,3,4]
輸出：[1,1,2,3,4,4]
示例 2：

輸入：l1 = [], l2 = []
輸出：[]
示例 3：

輸入：l1 = [], l2 = [0]
輸出：[0]

提示：
兩個鏈表的節(jié)點數目范圍是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非遞減順序 排列

這道題我看了力扣的官方解題思路后選擇了迭代法，那個動圖真的很形象，可以結合代碼理解：

/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {struct ListNode* pHead=(struct ListNode*)malloc(sizeof(struct ListNode));//動態(tài)分配一個節(jié)點以便找到合并后的鏈表；struct ListNode* pre=pHead;//pre在兩個鏈表中移動傳遞數值；while(l1!=NULL&&l2!=NULL){if(l1->val<l2->val){pre->next=l1;l1=l1->next;}else{pre->next=l2;l2=l2->next;}pre=pre->next;}pre->next=(l1==NULL)?l2:l1;//鏈表長度可能會不相同，將最長的鏈表最后一部分直接掛到已經排序好的鏈表后面return pHead->next; }

來個遞歸解法：
1，如果有一個鏈表為空，則返回那個非空鏈表；
2，若非空，如果l1的val小于等于l2的val，則讓l1的指針域指向l1->next和l2合并的有序鏈表（因為此時l1已經是合并后鏈表的頭節(jié)點了，只需要從l1的下一個節(jié)點開始和l2合并就可以了），并返回l1；否則，就讓l2的指針域指向l2->next和l1合并的有序鏈表，并返回l2；
代碼如下：

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/ class Solution { public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {if(!l1||!l2)return l1?l1:l2;if(l1->val<=l2->val){l1->next=mergeTwoLists(l1->next,l2);return l1;}else{l2->next=mergeTwoLists(l1,l2->next);return l2;}} };

總結

以上是生活随笔為你收集整理的21. 合并两个有序链表(C语言)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。