Fetch the repository succeeded.
package com.wujunshen.algorithm.leetcode.divide.conquer;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;
import lombok.extern.slf4j.Slf4j;
/**
* @author frank woo(吴峻申) <br>
* email:<a href="mailto:frank_wjs@hotmail.com">frank_wjs@hotmail.com</a> <br>
* @date 2022/7/1 11:11<br>
*/
@Slf4j
public class 合并k个已排序的链表 {
public static void main(String[] args) {
List<ListNode> lists = new ArrayList<>();
lists.add(new ListNode(4, new ListNode(5, new ListNode(1))));
lists.add(new ListNode(1, new ListNode(3, new ListNode(4))));
lists.add(new ListNode(2, new ListNode(6)));
ListNode result = mergeLists(lists);
int index = 0;
while (result != null && result.next != null) {
log.info("index {} value is:{}", index, result);
result = result.next;
index++;
}
}
/**
* k个链表归并排序
*
* @param lists
* @return
*/
private static ListNode mergeLists(List<ListNode> lists) {
if (lists == null || lists.isEmpty()) {
return null;
}
PriorityQueue<ListNode> queue =
new PriorityQueue<>(lists.size(), Comparator.comparingInt(o -> o.val));
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
for (ListNode node : lists) {
if (node != null) {
queue.add(node);
}
}
while (!queue.isEmpty()) {
tail.next = queue.poll();
tail = tail.next;
if (tail.next != null) {
queue.add(tail.next);
}
}
return dummy.next;
}
@Data
@NoArgsConstructor
@AllArgsConstructor
static class ListNode {
int val;
ListNode next;
ListNode(int value) {
this.val = value;
}
}
}
class Solution {
public 合并k个已排序的链表.ListNode mergeKLists(ArrayList<合并k个已排序的链表.ListNode> lists) {
if (lists == null || lists.isEmpty()) {
return null;
}
PriorityQueue<合并k个已排序的链表.ListNode> queue =
new PriorityQueue<>(lists.size(), Comparator.comparingInt(o -> o.val));
合并k个已排序的链表.ListNode dummy = new 合并k个已排序的链表.ListNode(0);
合并k个已排序的链表.ListNode tail = dummy;
for (合并k个已排序的链表.ListNode node : lists) {
if (node != null) {
queue.add(node);
}
}
while (!queue.isEmpty()) {
tail.next = queue.poll();
tail = tail.next;
if (tail.next != null) {
queue.add(tail.next);
}
}
return dummy.next;
}
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。