方法1 迭代

/*
struct ListNode {
     int val;
     ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
};
*/

class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode* head = new ListNode(0);
        ListNode* l3 = head;

        while(l1&&l2){
            if(l1->val>l2->val){
                swap(l1,l2);  // 避免重复写！！！！
            }
            l3->next =l1;
            l1 = l1->next;
            l3= l3->next;
        }
        if(l1) l3->next = l1;
        if(l2) l3->next = l2;
        return head->next;
    }
};

方法2 递归

class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        if(l1 == NULL) return l2;
        if(l2 == NULL) return l1;
        if(l1->val>l2->val){
            swap(l1,l2);  // 避免重复写！！！！

        }
            l1->next = merge(l1->next,l2);
            return l1;
    }
};