将两个有序链表合并为一个新的有序链表并返回. 新链表是通过拼接给定的两个链表的所有节点组成的.
示例:
输入: 1->2->4, 1->3->4
输出: 1->1->2->3->4->4
- public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
- if (l1 == null) {
- return l2 ;
- }
- if (l2 == null) {
- return l1;
- }
- ListNode dummy = new ListNode(-1);
- ListNode pre = dummy;
- while (l1 != null && l2 != null) {
- if (l1.val <l2.val) {
- pre.next = l1;
- l1 = l1.next;
- } else {
- pre.next = l2;
- l2 = l2.next;
- }
- pre = pre.next;
- }
- while (l1 != null) {
- pre.next = l1;
- }
- while (l2 != null) {
- pre.next = l2;
- }
- return dummy.next;
- }
合并 k 个排序链表, 返回合并后的排序链表. 请分析和描述算法的复杂度.
示例:
输入:
- [
- 1->4->5,
- 1->3->4,
- 2->6
- ]
输出: 1->1->2->3->4->4->5->6
- public class T23 {
- public ListNode mergeKLists(ListNode[] lists) {
- ListNode dummy = new ListNode(-1);
- ListNode pre = dummy;
- if (lists == null || lists.length == 0) {
- return dummy.next;
- }
- PriorityQueue<ListNode> que = new PriorityQueue<>(lists.length, new Comparator<ListNode>() {
- @Override
- public int compare(ListNode o1, ListNode o2) {
- return o1.val - o2.val;
- }
- });
- for (ListNode node : lists) {
- if (node != null) {
- que.add(node);
- }
- }
- while (!que.isEmpty()) {
- pre.next = que.poll();
- pre = pre.next;
- if (pre.next != null) {
- que.add(pre.next);
- }
- }
- return dummy.next;
- }
- }
弹出时, 比较的操作是 log(k),k 为链表的数目, 取得最小点的操作时间是 O(1). 一共有 n 个点. 故时间复杂度是 O(nlog(k)).
来源: http://www.bubuko.com/infodetail-3464620.html