写法一:在原链表上进行操作

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        if(!l1) return l2;
        else if(!l2) return l1;
        int size_l1 = 0,size_l2 = 0;
        for(auto i=l1;i;i=i->next) size_l1++;
        for(auto i=l2;i;i=i->next) size_l2++;
        if(size_l1<size_l2)
        {
            ListNode * t=l1;
            l1=l2;
            l2=t;
        }
        if(l1 && l2 && l1->val > l2->val)
        {
            auto t = l1->val;
            l1->val = l2->val;
            l2->val = t;
        }
        auto i=l1,t=l2;
        for(;i->next;)
        {
            if(t && t->val < i->next->val)
            {
                auto x = t->next,y=i;
                t->next = i->next;
                i->next = t;
                t=x;
                i=y;
            }
            else i=i->next;
        }
        if(t) i->next = t;
        return l1;
    }
};

写法二:new 一个新链表

利用归并排序的合并思想

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode * res = new ListNode(0);
        ListNode * temp =  res;
        while(l1 && l2)
        {
            if(l1->val < l2->val) 
            {
                temp->next = l1;
                l1=l1->next;
                temp=temp->next;
                temp->next=NULL;
            }
            else
            {
                temp->next = l2;
                l2=l2->next;
                temp=temp->next;
                temp->next=NULL;
            }
        }
        if(l1) temp->next = l1;
        if(l2) temp->next = l2;
        return res->next;
    }
};