题目
输入k个排序的链表,请将它们合并成一个排序的链表。
分析:利用最小堆选取值最小的节点
用k个指针分别指向这k个链表的头节点,每次从这k个节点中选取值最小的节点。然后将指向值最小的节点的指针向后移动一步,再比较k个指针指向的节点并选取值最小的节点。重复这个过程,直到所有节点都被选取出来。文章来源:https://www.toymoban.com/news/detail-772842.html
解
public class Test {
public static void main(String[] args) {
ListNode listNode1 = new ListNode(1);
ListNode listNode2 = new ListNode(2);
ListNode listNode3 = new ListNode(3);
ListNode listNode4 = new ListNode(4);
ListNode listNode5 = new ListNode(5);
ListNode listNode6 = new ListNode(6);
ListNode listNode7 = new ListNode(7);
ListNode listNode8 = new ListNode(8);
ListNode listNode9 = new ListNode(9);
listNode1.next = listNode4;
listNode4.next = listNode7;
listNode2.next = listNode5;
listNode5.next = listNode8;
listNode3.next = listNode6;
listNode6.next = listNode9;
ListNode[] lists = {listNode1, listNode2, listNode3};
ListNode result = mergeKLists(lists);
while (result != null) {
System.out.println(result.val);
result = result.next;
}
}
public static ListNode mergeKLists(ListNode[] lists) {
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
PriorityQueue<ListNode> minHeap = new PriorityQueue<>((n1, n2) -> n1.val - n2.val);
for (ListNode list : lists) {
if (list != null) {
minHeap.offer(list);
}
}
while (!minHeap.isEmpty()) {
ListNode least = minHeap.poll();
cur.next = least;
cur = least;
if (least.next != null) {
minHeap.offer(least.next);
}
}
return dummy.next;
}
}
分析:按照归并排序的思路合并链表
输入的k个排序链表可以分成两部分,前k/2个链表和后k/2个链表。如果将前k/2个链表和后k/2个链表分别合并成两个排序的链表,再将两个排序的链表合并,那么所有链表都合并了。合并k/2个链表与合并k个链表是同一个问题,可以调用递归函数解决。文章来源地址https://www.toymoban.com/news/detail-772842.html
解
public class Test {
public static void main(String[] args) {
ListNode listNode1 = new ListNode(1);
ListNode listNode2 = new ListNode(2);
ListNode listNode3 = new ListNode(3);
ListNode listNode4 = new ListNode(4);
ListNode listNode5 = new ListNode(5);
ListNode listNode6 = new ListNode(6);
ListNode listNode7 = new ListNode(7);
ListNode listNode8 = new ListNode(8);
ListNode listNode9 = new ListNode(9);
listNode1.next = listNode4;
listNode4.next = listNode7;
listNode2.next = listNode5;
listNode5.next = listNode8;
listNode3.next = listNode6;
listNode6.next = listNode9;
ListNode[] lists = {listNode1, listNode2, listNode3};
ListNode result = mergeKLists(lists);
while (result != null) {
System.out.println(result.val);
result = result.next;
}
}
public static ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) {
return null;
}
return mergeLists(lists, 0, lists.length);
}
private static ListNode mergeLists(ListNode[] lists, int start, int end) {
if (start + 1 == end) {
return lists[start];
}
int mid = (start + end) / 2;
ListNode head1 = mergeLists(lists, start, mid);
ListNode head2 = mergeLists(lists, mid, end);
return merge(head1, head2);
}
private static ListNode merge(ListNode head1, ListNode head2) {
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while (head1 != null && head2 != null) {
if (head1.val < head2.val) {
cur.next = head1;
head1 = head1.next;
}
else {
cur.next = head2;
head2 = head2.next;
}
cur = cur.next;
}
cur.next = head1 == null ? head2 : head1;
return dummy.next;
}
}
到了这里,关于面试算法78:合并排序链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!