合并两个有序链表
- 标签:字符串处理、前缀判断
题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1:
> 输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4]
示例 2:输入:l1 = [], l2 = [] 输出:[]
示例 3:
输入:l1 = [], l2 = [0] 输出:[0] 提示:
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100 l1 和 l2 均按 非递减顺序 排列
原题: LeetCode 21
思路及实现
方式一:迭代(推荐)
思路
我们可以用迭代的方法来实现上述算法。当 l1 和 l2 都不是空链表时,判断 l1 和 l2 哪一个链表的头节点的值更小,将较小值的节点添加到结果里,当一个节点被添加到结果里之后,将对应链表中的节点向后移一位
代码实现
Java版本
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int val) {
* this.val = val;
* }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode node = new ListNode(-1); // 创建一个临时节点作为结果链表的头节点
ListNode cur = node;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
cur.next = list1; // 将较小节点连接到结果链表
list1 = list1.next; // 移动指针到下一个节点
} else {
cur.next = list2;
list2 = list2.next;
}
cur = cur.next; // 移动当前节点指针到下一个节点
}
if (list1 != null) {
cur.next = list1; // 将剩下的节点连接到结果链表
}
if (list2 != null) {
cur.next = list2;
}
return node.next; // 返回结果链表的头节点
}
}
说明:
创建了一个临时节点作为结果链表的头节点。然后使用cur引用指向当前节点,通过遍历两个链表,比较节点的值,将较小节点连接到结果链表中,并将指针移向下一个节点。最后,将剩下的节点连接到结果链表的末尾。需要注意的是,最后返回的是结果链表的头节点
C语言版本
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
node->val = -1; // 创建一个临时节点作为结果链表的头节点
node->next = NULL;
struct ListNode* cur = node;
while (list1 != NULL && list2 != NULL) {
if (list1->val < list2->val) {
cur->next = list1; // 将较小节点连接到结果链表
list1 = list1->next; // 移动指针到下一个节点
} else {
cur->next = list2;
list2 = list2->next;
}
cur = cur->next; // 移动当前节点指针到下一个节点
}
if (list1 != NULL) {
cur->next = list1; // 将剩下的节点连接到结果链表
}
if (list2 != NULL) {
cur->next = list2;
}
struct ListNode* result = node->next; // 指向结果链表的头节点
free(node); // 释放临时节点的内存
return result;
}
说明: 在C语言中使用了头节点,并使用了指针操作来完成。
在算法中,我们创建了一个临时节点作为结果链表的头节点。然后使用cur指针指向当前节点,通过遍历两个链表,比较节点的值,将较小节点连接到结果链表中,并将指针移向下一个节点。最后,将剩下的节点连接到结果链表的末尾。
需要注意的是,最后返回的是结果链表的头节点,使用一个临时节点来保存结果链表的头节点可以简化操作。
在末尾,我们释放了临时节点的内存,以防止内存泄漏。
Python3版本
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
node = ListNode(-1) # 创建临时节点作为结果链表的头节点
cur = node
while list1 and list2:
if list1.val < list2.val:
cur.next = list1 # 将较小节点连接到结果链表
list1 = list1.next
else:
cur.next = list2
list2 = list2.next
cur = cur.next
cur.next = list1 or list2 # 将剩下的节点连接到结果链表
return node.next # 返回结果链表的头节点
说明: Python 三元表达式写法 A if x else B ,代表当 x=True 时执行 A ,否则执行 B 。
复杂度分析
- 时间复杂度:O(M+N),M, N分别标识list1和list2的长度
- 空间复杂度: O(1), 节点引用cur,常量级的额外空间
方式二:递归(不推荐)
思路
我们可以如下递归地定义两个链表里的 merge 操作(忽略边界情况,比如空链表等):
情况一 :list1[0]<list2[0],则 list1[0]+merge(list1[1:],list2)
其他情况 :list2[0]+merge(list1,list2[1:])
也就是说,两个链表头部值较小的一个节点与剩下元素的 merge 操作结果合并。
我们直接将以上递归过程建模,同时需要考虑边界情况。
如果 l1 或者 l2 一开始就是空链表 ,那么没有任何操作需要合并,所以我们只需要返回非空链表。否则,我们要判断 l1 和 l2 哪一个链表的头节点的值更小,然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空,递归结束
代码实现
Java版本
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// 如果l1为空,则直接返回l2作为合并后的链表
if (l1 == null) {
return l2;
}
// 如果l2为空,则直接返回l1作为合并后的链表
else if (l2 == null) {
return l1;
}
// 如果l1的值小于l2的值
else if (l1.val < l2.val) {
// 将l1的下一个节点与l2递归地合并
l1.next = mergeTwoLists(l1.next, l2);
return l1; // 返回合并后的链表头节点l1
}
// 如果l2的值小于等于l1的值
else {
// 将l2的下一个节点与l1递归地合并
l2.next = mergeTwoLists(l1, l2.next);
return l2; // 返回合并后的链表头节点l2
}
}
}
说明:
解法提供了递归方式来合并两个有序链表的操作。在算法中,首先处理特殊情况:如果l1为空,则直接返回l2作为合并后的链表;如果l2为空,则直接返回l1作为合并后的链表。接下来,判断l1和l2的值大小关系:如果l1的值小于l2的值,将l1的下一个节点与l2递归地合并,将合并结果作为l1的下一个节点,并返回l1作为合并后的链表头节点;如果l2的值小于等于l1的值,将l2的下一个节点与l1递归地合并,将合并结果作为l2的下一个节点,并返回l2作为合并后的链表头节点。最终,返回合并后的链表头节点。
C语言版本
#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
// 如果l1为空,则直接返回l2作为合并后的链表
if (l1 == NULL) {
return l2;
}
// 如果l2为空,则直接返回l1作为合并后的链表
else if (l2 == NULL) {
return l1;
}
// 如果l1的值小于l2的值
else if (l1->val < l2->val) {
// 将l1的下一个节点与l2递归地合并
l1->next = mergeTwoLists(l1->next, l2);
return l1; // 返回合并后的链表头节点l1
}
// 如果l2的值小于等于l1的值
else {
// 将l2的下一个节点与l1递归地合并
l2->next = mergeTwoLists(l1, l2->next);
return l2; // 返回合并后的链表头节点l2
}
}
说明:
在算法中,首先处理特殊情况:如果l1为空,则直接返回l2作为合并后的链表;如果l2为空,则直接返回l1作为合并后的链表。接下来,判断l1和l2的值的大小关系:如果l1的值小于l2的值,将l1的下一个节点与l2递归地合并,将合并结果作为l1的下一个节点,并返回l1作为合并后的链表头节点;如果l2的值小于等于l1的值,将l2的下一个节点与l1递归地合并,将合并结果作为l2的下一个节点,并返回l2作为合并后的链表头节点。最终,返回合并后的链表头节点。
Python3版本
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1: # 如果l1为空,则直接返回l2
return l2
elif not l2: # 如果l2为空,则直接返回l1
return l1
elif l1.val < l2.val: # 如果l1的值小于l2的值
l1.next = self.mergeTwoLists(l1.next, l2) # 递归地将l1的下一个节点与l2合并
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next) # 递归地将l2的下一个节点与l1合并
return l2
复杂度分析
- 时间复杂度:O(n+m),其中 n 和 m 分别为两个链表的长度。因为每次调用递归都会去掉 l1 或者 l2 的头节点(直到至少有一个链表为空),函数 mergeTwoList 至多只会递归调用每个节点一次。因此,时间复杂度取决于合并后的链表长度,即 O(n+m)。
- 空间复杂度:O(n+m),其中 n 和 m 分别为两个链表的长度。递归调用 mergeTwoLists 函数时需要消耗栈空间,栈空间的大小取决于递归调用的深度。结束递归调用时 mergeTwoLists 函数最多调用 n+m 次,因此空间复杂度为 O(n+m)。
总结
递归和迭代都可以用来解决将两个有序链表合并的问题。下面对比一下递归和迭代的解法特点:
递归解法 | 迭代解法 | |
---|---|---|
优点 | 简洁,易于理解和实现 | 不涉及函数递归调用,避免递归开销和栈溢出问题 |
缺点 | 可能产生多个函数调用,涉及函数调用开销和栈溢出问题 | 需要使用额外变量保存当前节点,增加代码复杂性 |
时间复杂度 | O(m+n),其中m和n分别是两个链表的长度 | O(m+n),其中m和n分别是两个链表的长度 |
空间复杂度 | O(m+n),其中m和n分别是两个链表的长度 | O(1) |
在实际应用中,如果链表较长,特别是超过系统栈的容量,采用迭代解法更为安全。而对于简短的链表,递归解法更为简洁和直观。
相似题目
题目 | 难度 | 链接 |
---|---|---|
LeetCode 21 合并两个有序链表 | 简单 | 链接 |
LeetCode 23 合并K个有序链表 | 困难 | 链接 |
LeetCode 88 合并两个有序数组 | 简单 | 链接 |
LeetCode 56 合并区间 | 中等 | 链接 |