Simple Java Solution with Merge Sort and in-place sort two lists


  • 0
    J
    public class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            if (lists.length == 0) return null;
            return mergeKLists(lists,0,lists.length-1);
        }
        
        public ListNode mergeKLists(ListNode[] lists, int pre, int post) {
            if (pre == post) return lists[pre];
            ListNode a = lists[pre];
            ListNode b = lists[post];
            if (post - pre >= 2) {
                int middle = pre + (post - pre) / 2;
                a = mergeKLists(lists,pre,middle);
                if (middle+1 != post) b = mergeKLists(lists,middle+1,post);
            }
            return mergeLists(a,b);
        }
        
        public ListNode mergeLists(ListNode a, ListNode b) {
            if (a == null) return b;
            if (b == null) return a;
            if (a.val > b.val) {
                b.next = mergeLists(a,b.next);
                return b;
                }
            else {
                a.next = mergeLists(a.next,b);
                return a;
            }
        }
    }
    

    The code divides the array into smaller pieces until there are only two ListNode left. Then it will sort these two arrays recursively.


Log in to reply
 

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