A java solution based on HeapSort


  • 0
    G
    import java.util.List;
    
    
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
     
     
    public class Solution {
        
        /*
         * Assume that lists[start..end] satisfy the definition of Heap except for lists[start]
         * This function adjust lists[start..end] to Heap
         * Note that both start and end index are inclusive, counted from 0
         */
        private void heapAdjust(List<ListNode> lists, int start, int end) {
            if (start >= end) {
                return;
            }
            ListNode temp = lists.get(start);
            for (int i = (start+1)*2-1; i <= end; i = (i+1)*2-1) {
                if (i < end && lists.get(i).val > lists.get(i + 1).val) {
                    i++;
                }
                if (temp.val <= lists.get(i).val) {
                    break;
                }
                lists.set(start, lists.get(i));
                start = i;
            }
            lists.set(start, temp);
        }
        
        /*
         * There are some tricky sample input: some linked lists are null
         * which cause 'mergeKLists' function crash
         * so this function process the raw input by removing the null lists from List<ListNode>
         */
        private void process(List<ListNode> lists) {
            for (int i = 0; i < lists.size(); i++) {
                if (lists.get(i) == null) {
                    lists.remove(i);
                    i--;
                }
            }
        }
        
        public ListNode mergeKLists(List<ListNode> lists) {
            ListNode newList = null, tail;
            process(lists);
            if (lists.size() == 0) {
                //After 'process' the parameter 'lists' may not have any linked list
                //so return a null reference
                return newList;
            }
            //adjusts the whole lists to Heap
            for (int i = (lists.size()-2)/2; i >= 0; i--) {
                heapAdjust(lists, i, lists.size() - 1);
            }
            newList = lists.get(0);
            tail = lists.get(0);
            lists.set(0, lists.get(0).next);
            while (lists.size() > 0) {
                if (lists.get(0) == null) {
                    if (lists.size() > 1) {
                        lists.set(0, lists.get(lists.size() - 1));
                        lists.remove(lists.size() - 1);
                    }
                    else {
                        break;
                    }
                }
                heapAdjust(lists, 0, lists.size() - 1);
                tail.next = lists.get(0);
                tail = tail.next;
                lists.set(0, lists.get(0).next);
            }
            tail.next = null;
            return newList;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.