题目

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

来源：21. 合并两个有序链表 - 力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

比较插入法

定义两个指针分别指向两个链表，比较两个指针所指向的值，选取值小的节点直接加入新链表，并将其指针向后移动
（直接把节点接上去，而不是用值建立新节点）

代码如下：

class Solution { 
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { 
        if (!l1)
            return l2;
        if (!l2)
            return l1;
        ListNode* ihead = new ListNode(0);
        ListNode* node = ihead;
        while (l1 && l2)
        {     
            if (l1->val > l2->val)    swap(l1, l2);
            node->next = l1;
            node = node->next;
            l1 = l1->next;
        }
        node->next = l1 ? l1 : l2;
        return ihead->next;
    }
};

结果：
在这里插入图片描述

递归法

递归比较两个链表头节点的值
使小的那个为l1（若反了，则交换顺序）
然后l1的下一个节点为mergeTwoLists(l1.next, l2)的返回值

代码如下：

class Solution { 
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { 
        if (l1 && l2)
        { 
            if(l1->val > l2->val)   swap(l1,l2);            
            l1->next = mergeTwoLists(l1->next, l2);
        }
        return l1 ? l1 : l2;
    }
};

结果：
在这里插入图片描述

相关测试用函数

#include <iostream>
#include <vector>
using namespace std;
struct ListNode { 
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) { }
};
ListNode* ListNodeInit(vector<int> a){   //用vector初始化链表
    ListNode* ihead = new ListNode(0);
    ListNode* node = ihead;
    for(auto p = a.begin();p != a.end();p++)
    { 
        node->next = new ListNode(*p);
        node = node->next;
    }
    return ihead->next;
};
void ListNodePrint(ListNode* l){     //打印链表
    while(l)  
    { 
        cout<<"-"<<l->val;
        l = l->next;
    }
    cout<<endl;
};
int main(){ 
    vector<int> nums1{ 1,3,4};
    vector<int> nums2{ 1,2,4};
    ListNode* l1 = ListNodeInit(nums1);
    ListNode* l2 = ListNodeInit(nums2);
    Solution so;
    ListNode* ans = so.mergeTwoLists(l1,l2);
    ListNodePrint(ans);
}