手机图片生成网页链接_国家企业信用信息公示系统(官网)_手机推广平台有哪些_武汉大学人民医院精神卫生中心

思路一：暴力解法

分别遍历两个链表，不断比较节点大小，将较小的放入新链表

/*** 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* list1, ListNode* list2) {//声明一个新链表的哨兵节点，并初始化其值为-1，其后继为空ListNode* list3 = new ListNode(-1);//构建三个指针分别指向链表1、链表2、新链表ListNode* p1 = list1;ListNode* p2 = list2;ListNode* p3 = list3;//当两链表均未遍历完，继续合并while(p1 != nullptr && p2 != nullptr){//将较小值优先放入新链表中if(p1->val < p2->val){p3->next = p1;p1 = p1->next;}else{p3->next = p2;p2 = p2->next;}p3 = p3->next;}//将还未遍历完的链表直接与新链表的尾部连接起来if(p1 != nullptr){p3->next = p1;}if(p2 != nullptr){p3->next = p2;}//返回新链表头结点的后继return list3->next;}
};

• 时间复杂度：O(n+m)
• 空间复杂度：O(1)

思路二：递归

class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {if (l1 == nullptr) {return l2;} else if (l2 == nullptr) {return l1;} else if (l1->val < l2->val) {l1->next = mergeTwoLists(l1->next, l2);return l1;} else {l2->next = mergeTwoLists(l1, l2->next);return l2;}}
};

• 时间复杂度：O(n+m)
• 空间复杂度：O(n+m)