设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 技术交流 › 数据结构与算法 › leetcode 23. Merge k Sorted Lists
返回列表 发新帖
查看: 1798|回复: 0

[学习笔记] leetcode 23. Merge k Sorted Lists

[复制链接]
Seawolf
发表于 2019-8-6 05:14:47 | 显示全部楼层 |阅读模式

马上注册，结交更多好友，享用更多功能^_^

您需要 登录 才可以下载或查看，没有账号？立即注册

x
6.jpg

用二叉堆来优化：

  1. /**
  2. * Definition for singly-linked list.
  3. * public class ListNode {
  4. *     int val;
  5. *     ListNode next;
  6. *     ListNode(int x) { val = x; }
  7. * }
  8. */
  9. class Solution {
  10.    
  11.     public ListNode mergeKLists(ListNode[] lists) {
  12.         
  13.         if(lists == null || lists.length == 0){
  14.             
  15.             return null;
  16.             
  17.         }
  18.    
  19.         PriorityQueue <ListNode> queue = new PriorityQueue<ListNode>(lists.length, (a,b) -> a.val - b.val);
  20.         
  21.         for(ListNode e: lists){
  22.             
  23.             if(e != null){
  24.                
  25.                 queue.add(e);
  26.                
  27.             }
  28.             
  29.         }
  30.         
  31.         ListNode ptr = new ListNode(0);
  32.         
  33.         ListNode head = ptr;
  34.         
  35.         while(!queue.isEmpty()){
  36.             
  37.             ptr.next = queue.poll();
  38.             
  39.             ptr = ptr.next;
  40.             
  41.             if(ptr.next != null){
  42.                
  43.                 queue.add(ptr.next);
  44.                
  45.             }
  46.             
  47.             
  48.         }
  49.         
  50.         return head.next;
  51.         
  52.     }
  53.    
  54. }

  56.    
复制代码



用 divide and conquer：


  1. /**
  2. * Definition for singly-linked list.
  3. * public class ListNode {
  4. *     int val;
  5. *     ListNode next;
  6. *     ListNode(int x) { val = x; }
  7. * }
  8. */
  9. class Solution {
  10.    
  11.     public ListNode mergeKLists(ListNode[] lists) {
  12.    
  13.         if(lists.length == 0){
  14.             
  15.             return null;
  16.         }
  17.         
  18.         if(lists.length == 1){
  19.             
  20.             return lists[0];
  21.         }
  22.         
  23.         if(lists.length == 2){
  24.             
  25.             return mergeSort(lists[0],lists[1]);
  26.         }
  27.         
  28.         
  29.         int mid;
  30.         
  31.         ListNode[] sublist1;
  32.         
  33.         ListNode[] sublist2;
  34.         
  35.         if(lists.length % 2 ==0){
  36.             
  37.             mid = lists.length/2;
  38.         
  39.             sublist1 = new ListNode[mid];
  40.         
  41.             sublist2 = new ListNode[mid];
  42.             
  43.         }
  44.         else{
  45.         
  46.             mid = lists.length/2;
  47.         
  48.             sublist1 = new ListNode[mid];
  49.         
  50.             sublist2 = new ListNode[mid+1];
  51.             
  52.         }
  53.         
  54.         for(int i = 0 ; i< mid ; i++){
  55.             
  56.             sublist1[i]  = lists[i];
  57.             
  58.         }
  59.         
  60.         
  61.         int count = 0;
  62.         
  63.         for(int i = mid ; i< lists.length ; i++){
  64.             
  65.             sublist2[count] = lists[i];
  66.             
  67.             count++;
  68.             
  69.         }
  70.         
  71.         ListNode l1 = mergeKLists(sublist1);
  72.         
  73.         ListNode l2 = mergeKLists(sublist2);
  74.         
  75.         return mergeSort(l1,l2);
  76.         
  77.     }
  78.    
  79.     private static ListNode mergeSort(ListNode l1, ListNode l2){
  80.         
  81.         ListNode ptr = new ListNode(0);
  82.             
  83.         ListNode head = ptr;
  84.         
  85.         while(l1 != null || l2 != null){
  86.             
  87.             if(l2 == null || (l1 != null && l2.val >= l1.val)){
  88.                
  89.                 ptr.next = l1;
  90.                
  91.                 l1 = l1.next;
  92.                
  93.                 ptr = ptr.next;
  94.                
  95.                
  96.             }
  97.             else if (l1 == null || (l2 != null && l1.val > l2.val)){
  98.                
  99.                 ptr.next = l2;
  100.                
  101.                 l2 = l2.next;
  102.                
  103.                 ptr = ptr.next;
  104.                
  105.             }
  106.             
  107.                
  108.         }
  109.         
  110.         return head.next;
  111.         
  112.     }
  113.    
  114. }

  116.    
复制代码



本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-4-27 22:12

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表