Description
將兩個(gè)有序鏈表合并為一個(gè)新的有序鏈表并返回雄妥。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的缴啡。
示例：
輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4
Analyze
給定的函數(shù)如下：
- @param l1 鏈表頭結(jié)點(diǎn)(帶值)
- @param l2 鏈表頭結(jié)點(diǎn)(帶值)
- @return 兩個(gè)鏈表連接的新鏈表頭結(jié)點(diǎn)(帶值)
既然兩個(gè)鏈表都是有序鏈表抖甘，那么可以從兩個(gè)鏈表開頭一個(gè)一個(gè)連接到新鏈表上爷绘，當(dāng)一個(gè)鏈表鏈完之后鲤屡，直接把另一個(gè)鏈表鏈到后面就行了
Realization
- 新鏈表頭指針
tmp是移動(dòng)的結(jié)點(diǎn)孝治，由他來判斷該鏈接哪個(gè)結(jié)點(diǎn)到新鏈表中列粪，p 是新鏈表的頭指針
- 主循環(huán)
先把其中一個(gè)鏈表遍歷完审磁，把值小的那個(gè)結(jié)點(diǎn)加入到新鏈表中
-
再把剩余的直接連接到tmp后面
-
返回
-
提交
附源代碼
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
struct ListNode* tmp = (struct ListNode*)malloc(sizeof(struct ListNode));
tmp->next = NULL;
struct ListNode* p = tmp;
while(l1 && l2)
{
if(l1->val < l2->val)
{
tmp->next = l1;
l1 = l1->next;
tmp = tmp->next;
}
else
{
tmp->next = l2;
l2 = l2->next;
tmp = tmp->next;
}
}
tmp->next = l1 ? l1 : l2;
return p->next;
}