脚本宝典收集整理的这篇文章主要介绍了合并k个排序列表,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
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 <= listsi <= 10^4 lists[i] 按 升序 排列 lists[i].length 的总和不超过 10^4
/** * 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) { if (lists == null || lists.length == 0) return null; // 将所有节点添加到数组中 List<ListNode> nodes = new ArrayList<>(); for (ListNode list : lists) { while (list != null) { nodes.add(list); list = list.next; } } // 对数组进行排序 nodes.sort((ListNode node1, ListNode node2) -> { return node1.val - node2.val; }); // 将排好序的节点串起来 ListNode head = new ListNode(0); ListNode cur = head; for (ListNode node: nodes) { cur = cur.next = node; } return head.next; } }
/** * 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) { if (lists == null || lists.length == 0) return null; ListNode head = new ListNode(0); ListNode cur = head; while (true) { // 最小链表节点所在的索引 int minIndex = -1; for (int i = 0; i < lists.length; i++) { if (lists[i] == null) continue; if (minIndex == -1 || lists[i].val < lists[minIndex].val) { minIndex = i; } } // 所有链表节点已经串起来了 if (minIndex == -1) break; cur = cur.next = lists[minIndex]; lists[minIndex] = lists[minIndex].next; } return head.next; } }
/** * 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) { if (lists == null || lists.length == 0) return null; for (int i = 1; i < lists.length; i++) { lists[0] = mergeTwoLists(lists[0], lists[i]); } return lists[0]; } // 虚拟头结点 PRivate ListNode head = new ListNode(0); public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) return l2; if (l2 == null) return l1; head.next = null; ListNode cur = head; while (l1 != null && l2 != null) { if (l1.val <= l2.val) { cur = cur.next = l1; l1 = l1.next; } else { cur = cur.next = l2; l2 = l2.next; } } if (l1 == null) { cur.next = l2; } else if (l2 == null) { cur.next = l1; } return head.next; } }
/** * 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) { if (lists == null || lists.length == 0) return null; ListNode head = new ListNode(0); ListNode cur = head; // 将所有的链表的头节点添加到小顶堆(优先级队列)中 PriorityQueue<ListNode> queue = new PriorityQueue<>((ListNode node1, ListNode node2) -> { return node1.val - node2.val; }); for (ListNode list: lists) { if (list == null) continue; queue.offer(list); } // 不断删除堆顶元素,并且把堆顶元素的next添加到堆中 while (!queue.iSEMpty()) { // 删除堆顶元素 ListNode node = queue.poll(); cur = cur.next = node; if (node.next != null) { queue.offer(node.next); } } return head.next; } }
/** * 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) { if (lists == null || lists.length == 0) return null; int step = 1; while (step < lists.length) { int nextStep = step << 1; for (int i = 0; i+step < lists.length; i += nextStep) { lists[i] = mergeTwoLists(lists[i], lists[i+step]); } step = nextStep; } return lists[0]; } // 虚拟头结点 private ListNode head = new ListNode(0); public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) return l2; if (l2 == null) return l1; head.next = null; ListNode cur = head; while (l1 != null && l2 != null) { if (l1.val <= l2.val) { cur = cur.next = l1; l1 = l1.next; } else { cur = cur.next = l2; l2 = l2.next; } } if (l1 == null) { cur.next = l2; } else if (l2 == null) { cur.next = l1; } return head.next; } }
以上是脚本宝典为你收集整理的合并k个排序列表全部内容,希望文章能够帮你解决合并k个排序列表所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。