https://www.nowcoder.com/questionTerminal/65cfde9e5b9b4cf2b6bafa5f3ef33fa6
ListNode
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
代码
package 合并k个已排序的链表;
import 合并k个已排序的链表.ListNode;
import java.util.*;
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
/*
取链表与rs链表合并：
若rs链表为空，直接插入rs
若该链表的首元素比rs链表的末元素大，直接排在rs后面;
若该链表的末元素比rs链表的首元素小，直接排在rs前面;
，否则正常合并两者
*/
public class Solution {
public static ListNode mergeKLists(ArrayList<ListNode> lists) {
ListNode rsHead = null; //结果链表的头指针
ListNode temp = null; //结果链表的临时节点
ListNode list1 = null;
ListNode temp1 = null;//链表1的节点
for (int i = 0; i < lists.size(); i++) {
list1 = lists.get(i);
if (list1 == null) {
continue;
}
temp1 = list1;
while (temp1.next != null) {
temp1 = temp1.next;
}
if (rsHead == null) {
rsHead = list1;
//找结果链表的末节点
temp = list1;
while (temp.next != null) {
temp = temp.next;
}
} else if (list1.val > temp.val) {
temp.next = list1;
//找结果链表的末节点
while (temp.next != null) {
temp = temp.next;
}
} else if (temp1.val < rsHead.val) {
temp1.next = rsHead;
rsHead = list1;
//找结果链表的末节点
while (temp.next != null) {
temp = temp.next;
}
} else {
temp = rsHead;
temp1 = list1;
ListNode rs2 = null;//头结点
ListNode temp2 = null;
//两条链表都没结束
while (temp != null && temp1 != null) {
if (temp.val <= temp1.val) {
if (rs2 == null) {
rs2 = new ListNode(temp.val);
temp2 = rs2;
} else {
temp2.next = new ListNode(temp.val);
temp2 = temp2.next;
}
temp = temp.next;
} else { //temp1.val < temp.val
if (rs2 == null) {
rs2 = new ListNode(temp1.val);
temp2 = rs2;
} else {
temp2.next = new ListNode(temp1.val);
temp2 = temp2.next;
}
temp1 = temp1.next;
}
}
//rs链表先结束
if (temp == null) {
while (temp1 != null) {
temp2.next = new ListNode(temp1.val);
temp2 = temp2.next;
temp1 = temp1.next;
}
} else if (temp1 == null) { //链表1先结束
while (temp != null) {
temp2.next = new ListNode(temp.val);
temp2 = temp2.next;
temp = temp.next;
}
}
rsHead = rs2;
temp = temp2;
}
}
return rsHead;
}
public static void main(String[] args) {
ArrayList<ListNode> lists = new ArrayList<>();
ListNode list1 = new ListNode(1);
ListNode temp1 = list1;
temp1.next = new ListNode(2);
temp1 = temp1.next;
temp1.next = new ListNode(2);
lists.add(list1);
ListNode list2 = new ListNode(1);
ListNode temp2 = list2;
temp2.next = new ListNode(1);
temp2 = temp2.next;
temp2.next = new ListNode(2);
lists.add(list2);
ListNode rs = mergeKLists(lists);
ListNode rsTemp = rs;
while (rsTemp != null) {
System.out.print(rsTemp.val + " ");
rsTemp = rsTemp.next;
}
}
}
代码
package 合并k个已排序的链表;
import java.util.ArrayList;
/**
* @author musecho801
* @title Solution1
* @description 合并k个已排序的链表：
* 将数组中链表两两合并，N个链表变成N/2个链表；循环，直到只有一个链表。
* 将问题规模由N变为N/2、N/4、。。1
* 注意：确保有偶数个节点
* @date 2021/3/10 18:41
*/
public class Solution1 {
/**
* @title mergeKLists
* @description 合并k个已排序的链表 主算法
* @date 2021/3/10 19:44
* @Param lists: 存放待排序链表的数组
* @return: ListNode
*/
public static ListNode mergeKLists(ArrayList<ListNode> lists) {
if (lists == null || lists.size() == 0) return null;
if (lists.size() == 1) return lists.get(0);
//确保链表为偶数个
if (lists.size() % 2 != 0)
lists.add(null);
ArrayList<ListNode> rsList = new ArrayList<>();//结果数组
for (int i = 0; i < lists.size(); i += 2) {
rsList.add(mergeTwoLists(lists.get(i), lists.get(i + 1)));
}
return mergeKLists(rsList);
}
/**
* @title mergeTwoLists
* @description 合并两个链表
* @date 2021/3/10 19:45
* @Param list1
* @Param list2
* @return: ListNode
*/
public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode list3 = new ListNode(0);//两个链表合并的结果链表
ListNode list4 = list3;//标注结果链表的头节点
while (list1 != null && list2 != null) {
if (list1.val <= list2.val) {
list3.next = list1;
list1 = list1.next;
} else {
list3.next = list2;
list2 = list2.next;
}
list3 = list3.next;
}
// while (list1 != null) {
// list3.next = new ListNode(list1.val);
// list3 = list3.next;
// list1 = list1.next;
// }
// while (list2 != null) {
// list3.next = new ListNode(list2.val);
// list3 = list3.next;
// list2 = list2.next;
// }
list3.next = list1 != null ? list1 : list2;
return list4.next;
}
public static void main(String[] args) {
ArrayList<ListNode> nodeArrayList = new ArrayList<>();
ListNode l1 = new ListNode(1);
nodeArrayList.add(l1);
l1.next = new ListNode(2);
l1 = l1.next;
l1.next = new ListNode(3);
ListNode l2 = new ListNode(4);
nodeArrayList.add(l2);
l2.next = new ListNode(5);
l2 = l2.next;
l2.next = new ListNode(6);
l2 = l2.next;
l2.next = new ListNode(7);
ListNode rs = mergeKLists(nodeArrayList);
while (rs != null) {
System.out.print(rs.val + " ");
rs = rs.next;
}
}
}
亮点
合并两条链表时，新建节点0，最后返回合并结果的头结点时返回该节点后面一个结点。
这段代码看起来我的那段合并代码清爽些。
ListNode list3 = new ListNode(0);//两个链表合并的结果链表
ListNode list4 = list3;//标注结果链表的头节点
。。。
return list4.next;
list3链接后面节点时，不需要一个一个节点遍历连接。
// while (list1 != null) {
// list3.next = new ListNode(list1.val);
// list3 = list3.next;
// list1 = list1.next;
// }
// while (list2 != null) {
// list3.next = new ListNode(list2.val);
// list3 = list3.next;
// list2 = list2.next;
// }
list3.next = list1 != null ? list1 : list2;
代码
package 合并k个已排序的链表;
import java.util.ArrayList;
/**
* @author musecho801
* @title Solution2
* @description 分治法：
* 数组一分为二，左半部分、右半部分的链表继续递归，然后两两合并
* @date 2021/3/10 23:05
*/
public class Solution2 {
public ListNode mergeKLists(ArrayList<ListNode> lists) {
if (lists.size() == 0) return null;
return mergeKLists(lists, 0, lists.size() - 1);
}
public ListNode mergeKLists(ArrayList<ListNode> lists, int low, int high) {
if (low == high) return lists.get(low);
// int mid = (low + high) / 2;
int mid = low + (high - low) / 2;
ListNode l1 = mergeKLists(lists, low, mid);
ListNode l2 = mergeKLists(lists, mid + 1, high);
return mergeTwoLists(l1, l2);
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null || l2 == null)
return l1 == null ? l2 : l1;
ListNode l3 = new ListNode(0);
ListNode l4 = l3;//标识合并的结果链表的头结点
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
l3.next = l1;
l1 = l1.next;
} else {
l3.next = l2;
l2 = l2.next;
}
l3 = l3.next;
}
l3.next = l1 != null ? l1 : l2;
return l4.next;
}
public static void main(String[] args) {
Solution2 solution2 = new Solution2();
ArrayList<ListNode> nodeArrayList = new ArrayList<>();
ListNode l1 = null;
nodeArrayList.add(l1);
ListNode l2 = new ListNode(-2);
nodeArrayList.add(l2);
ListNode l3 = null;
nodeArrayList.add(l3);
ListNode rs = solution2.mergeKLists(nodeArrayList);
while (rs != null) {
System.out.print(rs.val + " ");
rs = rs.next;
}
}
}
亮点
取mid的写法。
下面的写法能防止溢出，参考：https://blog.csdn.net/weixin_44556968/article/details/110288725
// int mid = (low + high) / 2;
int mid = low + (high - low) / 2;
代码
package 合并k个已排序的链表;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
/**
* @author musecho801
* @title Solution3
* @description 优先队列：
* 重写优先队列的排序规则使其升序，将数组中所有节点加入优先队列，
* 取优先队列中的首节点加入结果链表rs，将其下一个节点加入优先队列。
* @date 2021/3/11 11:50
*/
public class Solution3 {
public ListNode mergeKLists(ArrayList<ListNode> lists) {
if (lists.size() == 0) return null;
if (lists.size() == 1) return lists.get(0);
PriorityQueue<ListNode> que = new PriorityQueue<>(
new Comparator<ListNode>() {
@Override
public int compare(ListNode o1, ListNode o2) {
return o1.val - o2.val;
}
}
);
for (ListNode list : lists) {
if (list == null)
continue;
que.add(list);
}
ListNode rs = new ListNode(0);
ListNode rsHead = rs;
while (que.size() > 0) {
ListNode node = que.poll();
rs.next = node;
if (node.next != null) {
que.add(node.next);
}
rs = rs.next;
}
return rsHead.next;
}
public static void main(String[] args) {
Solution3 solution3 = new Solution3();
ArrayList<ListNode> nodeArrayList = new ArrayList<>();
ListNode l1 = new ListNode(1);
nodeArrayList.add(l1);
l1.next = new ListNode(2);
l1 = l1.next;
l1.next = new ListNode(3);
ListNode l2 = new ListNode(-1);
nodeArrayList.add(l2);
l2.next = new ListNode(0);
l2 = l2.next;
l2.next = new ListNode(1);
l2 = l2.next;
l2.next = new ListNode(2);
ListNode rs = solution3.mergeKLists(nodeArrayList);
while (rs != null) {
System.out.print(rs.val + " ");
rs = rs.next;
}
}
}
亮点
解法一：https://www.nowcoder.com/profile/853696206/codeBookDetail?submissionId=88248807
解法二：https://www.nowcoder.com/profile/688208353/codeBookDetail?submissionId=89021972
解法三：https://leetcode-cn.com/problems/merge-k-sorted-lists/comments/64343
原文：https://www.cnblogs.com/musecho/p/14517103.html