Why not merge sorted lists iteratively?


  • 0
    H

    I'm getting time out error for the below code. Can you help me understand what's wrong if we merge the list in the loop rather than the partition technique?

    public ListNode mergeKLists(ListNode[] lists) {
            if (lists == null || lists.length == 0) {
                return null;
            }
            int len = lists.length;
            ListNode head = null;
            for (int i = 0; i < len; i++) {
                head = merge(head, lists[i]);
            }
            return head;
            //return partition(lists, 0, lists.length-1);
        }
        
        public ListNode partition(ListNode[] lists, int start, int end) {
            if (start > end) {
                return null;
            }
            if (start == end) {
                return lists[start];
            }
            int mid = start + (end-start)/2;
            ListNode l1 = partition(lists, start, mid);
            ListNode l2 = partition(lists, mid+1, end);
            return merge(l1, l2);
        }
    
        public ListNode merge(ListNode l1, ListNode l2) {
            if (l1 == null) {
                return l2;
            }
            if (l2 == null) {
                return l1;
            }
            
            if (l1.val < l2.val) {
                l1.next = merge(l1.next, l2);
                return l1;
            } else {
                l2.next = merge(l1, l2.next);
                return l2;
            }
        }

Log in to reply
 

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