Recursion based method (updated parameter ListNode[] lists) using copyOfRange.


  • 0
    S

    Credit goes to the orgininal recursion version. I just updated the code to adapt the new paramenter setting.

    public class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            
            if (lists.length == 0) return null;
            if (lists.length == 1) return lists[0];
            if (lists.length == 2) return mergeTwoLists(lists[0], lists[1]);
            
            return mergeTwoLists(mergeKLists(Arrays.copyOfRange(lists, 0, lists.length/2)), mergeKLists(Arrays.copyOfRange(lists,lists.length/2, lists.length)));
            
        }
        
        private ListNode mergeTwoLists(ListNode l1, ListNode l2){
            ListNode l = new ListNode(0), p = l;
            
            while (l1 != null && l2 != null){
                if (l1.val <= l2.val){
                    p.next = l1;
                    l1 = l1.next;
                }
                else {
                    p.next = l2;
                    l2 = l2.next;
                }
                p = p.next;
            }
            
            if (l1 != null) p.next = l1;
            if (l2 != null) p.next = l2;
            
            return l.next;
        }
    

Log in to reply
 

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