# LeetCode – Merge Two Sorted Lists

## 题目：

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.

Example:

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

## 解题：

新申请哨兵节点重组新的链表返回 。 比较两个链表选择较小的接入新链表，对于较长的链表，将其剩余部分接到新链表的尾部。

## 实现：

``````struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
struct ListNode* result = (struct ListNode *)malloc(sizeof(struct ListNode) );
if (result == NULL){
return NULL;
}
result->next = NULL;
struct ListNode* l3 = result;

while(l1!=NULL && l2!=NULL){
if (l1->val<l2->val){
l3->next = l1;
l1= l1->next;
l3= l3->next;
}else{
l3->next = l2;
l2= l2->next;
l3= l3->next;

}
}
if (l1!=NULL){
l3->next = l1;
}
else if (l2!=NULL){
l3->next = l2;
}

return result->next;
}``````

``````struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
if(!l1){
return l2;
}
if(!l2){
return l1;
}
if (l1->val < l2->val){
l1->next = mergeTwoLists(l1->next, l2);
return l1;
}
else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
``````