21. 合并两个有序链表（C++）
2021-04-02 06:25
标签：text otherwise 示例 一个 返回 struct 操作 lse 决定 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例： 在忽略空链表的情况下，利用递归的思想依次对两个链表的元素进行比较和合并，大致思路如下： 也就是说，两个链表头部值较小的一个节点与剩下元素的 代码如下： 21. 合并两个有序链表（C++） 标签：text otherwise 示例 一个 返回 struct 操作 lse 决定 原文地址：https://www.cnblogs.com/buryinshadow/p/13502555.html
题目
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
分析与题解
merge 操作结果合并。如果 l1 或者 l2 一开始就是空链表 ，那么没有任何操作需要合并，所以我们只需要返回非空链表。否则，我们要判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空，递归结束。/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
//如果某个指针为空指针，直接返回飞空指针即可
if(l1 == nullptr)
return l2;
else if(l2 == nullptr)
return l1;
else if(l1->val val){
l1->next = mergeTwoLists(l1->next,l2);
return l1;
}
else{
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
};