# LeetCode -  Merge Two Sorted Lists
Date: 2019-05-12


## 题目：

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;
}
```

递归方式：比较两个链表当前节点较小节点，这个结点的next节点与另外一个链表的当前节点比较，更新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;
    }
}
```