# Merge Two Sorted Lists

## Merge Two Sorted Lists

原题链接：[Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/)

### 描述

> Merge two sorted linked lists and return it as a new **sorted** list. The new list should be made by splicing together the nodes of the first two lists.

### 例子

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

### 解法一

```
class Solution {
public:
   ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode *tail = &dummy;
        while(l1 && l2) {
            ListNode *& node = l1->val < l2->val ? l1 : l2;
            tail = tail->next = node;
            node = node->next;
        }
        tail->next = l1 ? l1 : l2;
        return dummy.next;
    }
};
```

### 解法二

递归

```
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* a, ListNode* b) {
    if (!a || b && a->val > b->val) swap(a, b);
    if (a) a->next = mergeTwoLists(a->next, b);
    return a;
    }
};
```