题目描述：

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.

思路：

• 通过一个指针 newhead 指示新的链表头部，比较链表 l1 和链表 l2 的第一个结点；
• 若 l1 的第一个节点比 l2 小，则将其尾插进新链表，移动指针 l1->next；若 l2 的第一个节点比 l1 小，同理；
• 递归得解。

代码实现：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1==nullptr&&l2==nullptr)
            return nullptr;
        if(l1==nullptr || l2==nullptr)
            return (l1==nullptr)?l2:l1;
            
        ListNode* newhead=nullptr;
        if((l1->val)<=(l2->val)){
            newhead=l1;
            newhead->next = mergeTwoLists(l1->next,l2);
        }else{
            newhead=l2;
            newhead->next = mergeTwoLists(l1,l2->next);
        }
        return newhead;
    }
};