3ms java solution, nlogn complexity


  • 2
    R
    public class Solution {
        ListNode dummy;
        public ListNode mergeKLists(ListNode[] lists) {
            if(lists.length == 0) return null;
            dummy = new ListNode(0);
            int i = 0;
            int j = lists.length - 1;
            while(j!=0) {
                while(i < j) {
                    lists[i] = mergeTwo(lists[i++], lists[j--]);
                }
                i = 0;
            }
            return lists[0];
        }
        private ListNode mergeTwo(ListNode node1, ListNode node2) {
            ListNode head = dummy;
            while(node1 !=null && node2 != null) {
                if(node1.val < node2.val) {
                    head.next  = node1;
                    node1 = node1.next;
                }else {
                    head.next = node2;
                    node2 = node2.next;
                }
                head = head.next;
            }
            if(node1 != null) {
                head.next = node1;
            }
            if(node2 != null) {
                head.next = node2;
            }
            return dummy.next;
        }
    }

Log in to reply
 

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