O(NlogN) Java Solution with ArrayList, merge sort style


  • 0
    W

    class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
    // merge odd and even untill one left

        //time complexity is O(NlogN);space complecity is O(N)
        if(lists==null||lists.length==0) return null;
        
        List<ListNode> list= new ArrayList<ListNode>(Arrays.asList(lists));
        while(list.size()>1){
          
                ListNode l1=list.remove(0);
                ListNode l2=list.remove(0);
              ListNode merged= merge(l1,l2);
            list.add(merged);
            
            
        }
        return list.remove(0);
    }
    
    ListNode merge(ListNode l1, ListNode l2){
       
        ListNode h1=l1,h2=l2,dummy=new ListNode(1),cur=dummy;
        while(h1!=null &&h2!=null){
            if(h1.val<h2.val){
                cur.next=h1;
                    cur=h1;
                h1=h1.next;
            }else{
                cur.next=h2;
                cur=h2;
                h2=h2.next;
            }
        }
        if(h1==null) cur.next=h2;
        if(h2==null) cur.next=h1;
        return dummy.next;
    }
    

    }


Log in to reply
 

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