034合并K个升序链表

合并K个升序链表题目链接https://leetcode.cn/problems/merge-k-sorted-lists/description/?envTypestudy-plan-v2envIdtop-100-liked我的解答public ListNode mergeKLists(ListNode[] lists) { int length lists.length; if(length0 ||length1){ return length0 ? null : lists[0]; } ListNode dummyHead new ListNode(0); ListNode p1, p2, pre; for(int i0; ilength; i){ p1 dummyHead.next; p2 lists[i]; pre dummyHead; while(p1!null p2!null){ if(p1.valp2.val){ pre.next p1; p1 p1.next; } else{ pre.next p2; p2 p2.next; } pre pre.next; } if(p1!null){ pre.next p1; } else{ pre.next p2; } } return dummyHead.next; }分析假设每个链表的最长长度是n则代码的时间复杂度为O(k*n^2)空间复杂度为O(1)。解题思路让这k个升序链表按顺序一个个的进行合并。看了官方题解后的解答//方法一顺序合并(方法一与我的解答思路一致) //时间复杂度O(k*n^2) //空间复杂度O(1) //方法二分治合并 //时间复杂度O(kn*logk) //空间复杂度O(1) public ListNode mergeKLists(ListNode[] lists) { int length lists.length; if(length0 || length1){ return length0 ? null : lists[0]; } //step每轮分组的链表个数 for(int step1; steplength; step1){ for(int i0, jistep; jlength; i2*step, j2*step){ lists[i] mergeTwoLists(lists[i],lists[j]); } } return lists[0]; } //合并两个有序链表并返回头节点 public ListNode mergeTwoLists(ListNode head1, ListNode head2){ if(head1null || head2null){ return head1null ? head2 : head1; } ListNode dummy new ListNode(0); ListNode pre dummy; while(head1!null head2!null){ if(head1.valhead2.val){ pre.next head1; head1 head1.next; } else{ pre.next head2; head2 head2.next; } pre pre.next; } pre.next head1null ? head2 : head1; return dummy.next; } //方法三使用优先队列合并 //时间复杂度O(kn*logk) //空间复杂度O(k) public ListNode mergeKLists(ListNode[] lists) { int length lists.length; if(length0 || length1){ return length0 ? null : lists[0]; } ListNode dummyHead new ListNode(0); ListNode pre dummyHead, cur; PriorityQueueListNode queue new PriorityQueue((ListNode a, ListNode b) - a.val-b.val); for(int i0; ilength; i){ if(lists[i]!null){ queue.add(lists[i]); } } while(!queue.isEmpty()){ cur queue.poll(); pre.next cur; pre pre.next; if(cur.next!null){ queue.add(cur.next); } } return dummyHead.next; }分析​ 1、对于时间复杂度和空间复杂度的计算n为假设的每个链表的最长长度。​ 2、方法二采用分治合并。官方题解采用的是自顶向下的递归方式实现而我在看了题解思路之后采用了自底向上的方式实现以此降低空间复杂度。大致思路step为每组链表的个数初始值为1每轮都让相邻两组链表合并然后用合并后的新链表的头节点更新数组lists每轮结束后step*2直到step不小于链表总个数就可以实现k个链表的合并。​ 3、方法三采用优先队列优先队列按照节点值升序排序。首先将每个链表的头节点存入优先队列每次从队头出队一个节点将此节点合并入新链表并将这个节点的next入队重复此操作直至队列为空即可完成k个链表的合并。总结本题可采用顺序合并、分治合并、利用优先队列合并三种方法。合并思路都较为简单只需掌握两个有序链表的合并即可轻松实现这三种方式来完成k个链表的合并。