原题地址:. - 力扣(LeetCode)
题目描述
给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。
示例 1:
输入:lists = [[1,4,5],[1,3,4],[2,6]] 输出:[1,1,2,3,4,4,5,6] 解释:链表数组如下: [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6示例 2:
输入:lists = [] 输出:[]示例 3:
输入:lists = [[]] 输出:[]提示:
k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i]
按 升序 排列lists[i].length
的总和不超过10^4
实现思路
题目要求合并
k
个升序链表,返回一个升序的新链表。可以使用以下思路来解决这个问题:思路:
- 提取节点值:遍历所有链表,将每个节点的值提取到一个数组或列表中。
- 排序:对提取出的节点值进行排序。
- 构建新链表:使用排序后的值构建一个新的升序链表。
源码实现
/**
* 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 mergeKLists(ListNode[] lists) {
// 初始化结果链表
ListNode result = null;
// 如果输入链表数组为空,直接返回null
if (lists == null || lists.length == 0) {
return result;
}
// 使用一个列表来存储所有链表中的节点值
List<Integer> array = new ArrayList<>();
// 遍历所有链表,将节点值添加到列表中
for (int i = 0; i < lists.length; i++) {
node(lists[i], array);
}
// 如果列表为空,返回null
if (array.size() == 0) {
return result;
}
// 将列表转换为数组并排序
Integer[] ts = array.toArray(new Integer[array.size()]);
Arrays.sort(ts);
// 创建新链表的头节点
result = new ListNode(ts[0]);
ListNode dummy = result; // 使用dummy指针帮助构建链表
// 遍历排序后的数组,构建链表
for (int i = 1; i < ts.length; i++) {
ListNode temp = new ListNode(ts[i]);
dummy.next = temp; // 将新节点连接到链表
dummy = temp; // 移动dummy指针
}
return result; // 返回合并后的链表
}
// 辅助函数:遍历链表并将节点值添加到列表中
public void node(ListNode node, List<Integer> list) {
while (node != null) {
list.add(node.val); // 将节点值添加到列表
node = node.next; // 移动到下一个节点
}
}
}
复杂度分析
标签:ListNode,val,lists,链表,升序,节点,LeetCode23 From: https://blog.csdn.net/qq_36070104/article/details/143438179
时间复杂度:
- 提取所有链表中的值需要
O(N)
,其中N
是所有链表节点的总数。- 排序的时间复杂度为
O(N log N)
,因此整体时间复杂度为O(N log N)
。空间复杂度:
- 使用
O(N)
的空间存储所有节点的值。- 另外还需要
O(1)
的空间来构建新的链表(指针变量),所以总体空间复杂度为O(N)
。