原题地址:. - 力扣(LeetCode)
题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 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
均按 非递减顺序 排列
实现思路
- 输入检查:首先检查两个链表的头节点。如果一个链表为空,直接返回另一个链表的头节点。
- 优先队列(最小堆):使用一个优先队列来存储两个链表中的节点。通过重写比较器,确保队列中的节点按值升序排列。
- 遍历链表:将两个链表中的所有节点依次加入优先队列。在添加节点后,断开当前节点与后继节点的连接,以避免内存泄漏。
- 构建合并链表:从优先队列中依次取出节点,构建合并后的链表。使用一个临时节点指针来维护链表的尾部。
- 返回结果:返回合并后链表的头节点。
源码实现
/**
* 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) {
// 检查链表是否为空
if (l1 == null) { return l2; } // 如果l1为空,返回l2
if (l2 == null) { return l1; } // 如果l2为空,返回l1
// 使用优先队列来存储链表节点
PriorityQueue<ListNode> node = new PriorityQueue<>(new Comparator<ListNode>() {
@Override
public int compare(ListNode o1, ListNode o2) {
return o1.val - o2.val; // 按节点值升序排列
}
});
// 遍历两个链表并将节点加入优先队列
while (l1 != null || l2 != null) {
if (l1 != null) {
node.add(l1); // 添加l1节点
ListNode next = l1.next; // 记录下一个节点
l1.next = null; // 断开当前节点与后继的连接
l1 = next; // 移动到下一个节点
}
if (l2 != null) {
node.add(l2); // 添加l2节点
ListNode next = l2.next; // 记录下一个节点
l2.next = null; // 断开当前节点与后继的连接
l2 = next; // 移动到下一个节点
}
}
// 从优先队列中取出节点构建合并链表
ListNode result = node.poll(); // 取出第一个节点作为合并链表的头
ListNode temp = result; // 使用temp指针维护合并链表的尾部
while (node.peek() != null) {
ListNode tag = node.poll(); // 取出下一个节点
temp.next = tag; // 将当前节点链接到合并链表的尾部
temp = tag; // 更新temp指针
}
return result; // 返回合并后的链表头
}
}
复杂度分析
标签:ListNode,合并,next,链表,l2,l1,Leetcode21,节点 From: https://blog.csdn.net/qq_36070104/article/details/143416965
时间复杂度:O((m + n) log(m + n)),其中 m 和 n 分别是两个链表的长度。我们将所有节点加入优先队列的时间复杂度为 O(m + n),而每次从优先队列中取出节点的时间复杂度为 O(log(m + n)),因此总体复杂度为 O((m + n) log(m + n))。
空间复杂度:O(m + n),我们在优先队列中存储了两个链表的所有节点,因此需要 O(m + n) 的空间。