题目描述

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

题目链接

合并k个升序链表

测试用例

输入：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

输入：lists = []
输出：[]

输入：lists = [[]]
输出：[]

1. 顺序合并

思路

1. 定义两个链表合并的函数
2. 依次合并两个链表
   1. 先定义一个链表result为null
   2. 遍历ListNode数组，合并ListNode数组中遍历到的ListNode与result

代码

/*** 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;for(ListNode list : lists){//合并lists[i]与resultresult = mergeTwoLists(result, list);}return result;}//合并两个listpublic ListNode mergeTwoLists(ListNode list1, ListNode list2){ListNode resultReturn = new ListNode(0);ListNode result = resultReturn;while(list1!=null || list2!=null){int val1 = list1!=null ? list1.val : (int)Math.pow(10,4)+1;int val2 = list2!=null ? list2.val : (int)Math.pow(10,4)+1;if(val1 > val2){result.next = list2;result = result.next;list2 = list2.next;}else{result.next = list1;result = result.next;list1 = list1.next;}}return resultReturn.next;}
}

2. 分治

3. 优先队列

改天补充

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！