LeetCode 23. Merge k Sorted Lists

男娘i 2022-05-11 14:34 114阅读 0赞

Merge *k* sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

**Example:**

Input:
    [
      1->4->5,
      1->3->4,
      2->6
    ]
    Output: 1->1->2->3->4->4->5->6

hard

discuss中解法1：使用优先队列

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            
            if(lists==null || lists.length==0) return null;
            
            PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length, new Comparator<ListNode>(){
                public int compare(ListNode l1, ListNode l2){
                    return l1.val - l2.val;
                };
            });
            
            ListNode dummy = new ListNode(0);
            ListNode tail = dummy;
            
            //相当于初始化优先队列，将每一个链表的头结点放入队列，将会从小到大排序
            for(ListNode l : lists){
                if(l!=null)
                    pq.offer(l);
            }
            
            //队列不为空时，tail指向队首，然后将弹出的队首所在链表看是否还有节点，有则继续加入队列
            //队列中每次只保留每个链表的头结点
            while(!pq.isEmpty()){
                tail.next = pq.poll();
                tail = tail.next;
                
                if(tail.next!=null){
                    pq.offer(tail.next);
                }
            }
            
            return dummy.next;
        }
    }

submission中解法2：分解成子问题，最终使用二分归并排序算法

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            return divide(lists, 0, lists.length - 1);
        }
        
        private ListNode divide(ListNode[] lists, int start, int end){
            if(start > end){
                return null;
            }
            if(start == end){
                return lists[start];
            }
            
            int mid = start + (end - start) / 2;
            ListNode left = divide(lists, start, mid);
            ListNode right = divide(lists, mid + 1, end);
            return merge(left, right);
        }
        
        private ListNode merge(ListNode l1, ListNode l2){
            ListNode head = new ListNode(0);
            ListNode curr = head;
            while(l1 != null || l2 != null){
                if(l1 != null && l2 != null){
                    if(l1.val < l2.val){
                        curr.next = l1;
                        l1 = l1.next;
                    }else{
                        curr.next = l2;
                        l2 = l2.next;
                    }
                }else if(l1 != null){
                    curr.next = l1;
                    l1 = l1.next;
                }else{
                    curr.next = l2;
                    l2 = l2.next;
                }
                curr = curr.next;
            }
            return head.next;
        }
        
    }