分治 23.合并K的升序链表
给你一个链表数组,每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中,返回合并后的链表。
示例 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
代码
package ski.mashiro.leetcode;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
public class _23 {
/**
* 23. 合并K个升序链表
* <p>
* 给你一个链表数组,每个链表都已经按升序排列。
* 请你将所有链表合并到一个升序链表中,返回合并后的链表。
*/
public static void main(String[] args) {
ListNode l1 = new ListNode(1, new ListNode(4, new ListNode(5)));
ListNode l2 = new ListNode(1, new ListNode(3, new ListNode(4)));
ListNode l3 = new ListNode(2, new ListNode(6));
ListNode listNode = mergeKLists(new ListNode[]{l1, l2, l3});
while (listNode != null) {
System.out.print(listNode.val + ", ");
listNode = listNode.next;
}
}
/**
* 分治
* 每次将两个链表合并成一个
*/
public static ListNode mergeKLists(ListNode[] lists) {
return merge(lists, 0, lists.length - 1);
}
private static ListNode merge(ListNode[] lists, int left, int right) {
// 左右指针指向同一元素,直接返回
if (left == right) {
return lists[left];
}
// 因为mid + 1,有可能发生左指针大于右指针的情况
// 返回null
if (left > right) {
return null;
}
// 注释的是问题代码,目测是在向下舍入的时候有精度问题,导致无限递归
// int mid = (right - left) >> 1 + left;
int mid = (left + right) >> 1;
// 递归调用,递归返回数组的元素或是null,两者再进行合并,返回到上层递归称为参数
return mergeTwoListNode(merge(lists, left, mid), merge(lists, mid + 1, right));
}
/**
* 法二
* 新建一个链表,每次将新链表和数组内的一个链表合并
*/
public static ListNode mergeKLists2(ListNode[] lists) {
List<Integer> list = new ArrayList<>(lists.length * 5);
ListNode rs = null;
for (ListNode listNode : lists) {
rs = mergeTwoListNode(rs, listNode);
}
return rs;
}
private static ListNode mergeTwoListNode(ListNode list1, ListNode list2) {
ListNode rs = new ListNode();
ListNode cur = rs;
while (list1 != null || list2 != null) {
if (list1 != null && list2 != null) {
if (list1.val < list2.val) {
cur.next = list1;
list1 = list1.next;
} else {
cur.next = list2;
list2 = list2.next;
}
} else if (list1 != null) {
cur.next = list1;
list1 = list1.next;
} else {
cur.next = list2;
list2 = list2.next;
}
cur = cur.next;
}
return rs.next;
}
/**
* 法三
* 转换成集合处理
*/
public static ListNode mergeKLists3(ListNode[] lists) {
List<Integer> list = new ArrayList<>(lists.length * 5);
for (ListNode listNode : lists) {
while (listNode != null) {
list.add(listNode.val);
listNode = listNode.next;
}
}
list.sort(Comparator.comparingInt(o -> o));
ListNode rs = new ListNode();
ListNode cur = rs;
for (Integer item : list) {
cur.next = new ListNode(item);
cur = cur.next;
}
return rs.next;
}
private static class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
}