將兩個有序鏈表合并為一個新的有序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的依沮。
示例：
輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4
解法1（遞歸）：
思路： 初始化一個頭節(jié)點head，兩個鏈表的第一個節(jié)點比較，取較小的節(jié)點連接在head上危喉，使用遞歸的方法使除去該節(jié)點的兩個鏈表重復上述步驟宋渔，直至一個鏈表結束（或同時結束），最后返回head頭節(jié)點辜限。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
struct ListNode* head;
if(l1==NULL){
return l2;
}else if(l2==NULL){
return l1;
}
if(l1->val<l2->val){
head=l1;
head->next=mergeTwoLists(l1->next,l2);
}else{
head=l2;
head->next=mergeTwoLists(l1,l2->next);
}
return head;
}
解法2：
思路： 與上面算法思路相似皇拣，只是下面算法沒有使用遞歸。該算法需注意這句（ tail->next=l1 ? l1 : l2 ;）薄嫡，這句處理的是比較后氧急，有剩余節(jié)點的鏈表拼接在tail后
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
{
struct ListNode *head,*tail;
if(l1==NULL)
return l2;
else if(l2==NULL)
return l1;
if(l1->val<l2->val)
{
head=l1;
l1=l1->next;
}
else
{
head=l2;
l2=l2->next;
}
tail=head;
while(l1 && l2)
{
if(l1->val < l2->val)
{
tail->next=l1;
l1=l1->next;
}
else
{
tail->next=l2;
l2=l2->next;
}
tail=tail->next;
}
tail->next=l1?l1:l2;
return head;
}
