(链表) 剑指 Offer 25. 合并两个排序的链表 —

(链表) 剑指 Offer 25. 合并两个排序的链表 ——【Leetcode每日一题】

news/2023/11/29 6:59:02

❓剑指 Offer 25. 合并两个排序的链表

难度：简单

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

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

限制：

0 <= 链表长度 <= 1000

注意：本题与 21. 合并两个有序链表相同

💡思路：

法一：递归

将该问题可以分解成子链表，只比较当前 l1 链表和 l2 链表的头结点，取最小加入合并的链表中，并将最小结点的来自的链表的头结点往后移一位，在递归调用 mergeTwoLists 函数。

法二：迭代

我们可以用迭代的方法来实现上述算法。当 l1 和 l2 都不是空链表时，判断 l1 和 l2 哪一个链表的头节点的值更小，将较小值的节点添加到结果里，当一个节点被添加到结果里之后，将对应链表中的节点向后移一位。

🍁代码：(C++、Java)

法一：递归
C++

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {if(l1 == nullptr) return l2;if(l2 == nullptr) return l1;if(l1->val < l2->val){l1->next = mergeTwoLists(l1->next, l2);return l1;}else{l2->next = mergeTwoLists(l1, l2->next);return l2;}}
};

Java

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {if(l1 == null) return l2;if(l2 == null) return l1;if(l1.val < l2.val){l1.next = mergeTwoLists(l1.next, l2);return l1;}else{l2.next = mergeTwoLists(l1, l2.next);return l2;}}
}

法二：迭代
C++

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {if(l1 == nullptr) return l2;if(l2 == nullptr) return l1;//先找到头结点ListNode* head = nullptr;if(l1->val <= l2->val){head = l1;l1 = l1->next;}else{head = l2;l2 = l2->next;}//合并ListNode* cur = head;while(l1 != nullptr && l2 != nullptr){if(l1->val < l2->val){cur->next = l1;l1 = l1->next;}else{cur->next = l2;l2 = l2->next;}cur = cur->next;}if(l1 == nullptr){cur->next = l2;}else{cur->next = l1;}return head;}
};

Java

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {if(l1 == null) return l2;if(l2 == null) return l1;//先找到头结点ListNode head = null;if(l1.val <= l2.val){head = l1;l1 = l1.next;}else{head = l2;l2 = l2.next;}//合并ListNode cur = head;while(l1 != null && l2 != null){if(l1.val < l2.val){cur.next = l1;l1 = l1.next;}else{cur.next = l2;l2 = l2.next;}cur = cur.next;}if(l1 == null){cur.next = l2;}else{cur.next = l1;}return head;}
}

🚀 运行结果：

在这里插入图片描述

🕔 复杂度分析：

时间复杂度： $O (n + m)$ ，其中 n 和 m 分别为两个链表的长度。
空间复杂度： $O (1)$ ，迭代法只需要常数的空间存放若干变量。而法一递归的空间复杂度为 $O (n + m)$ ，递归调用 mergeTwoLists 函数时需要消耗栈空间，栈空间的大小取决于递归调用的深度。结束递归调用时 mergeTwoLists 函数最多调用 n+m 次，因此空间复杂度为 $O (n + m)$ 。