Straight forward Java code using basic data structure without recursion.


  • 0
    T

    Using basic data structure without recursion. Use the list size at the beginning of each loop as a counter.

    public ListNode mergeKLists(ArrayList<ListNode> lists) {
            if(lists.size()==0) return null;
            while(lists.size()>1){
                int n=lists.size();
                //Two lists are merged everytime ==>i+=2 (two lists removed with a merged list added) 
                for(int i=0;i<n-1;i+=2){
                    ListNode l1=lists.get(0);
                    ListNode l2=lists.get(1);
                    ListNode head=new ListNode(0);
                    ListNode tmp=head;
                    while(l1!=null||l2!=null){
                        if(l1==null) {
                            tmp.next=l2;
                            break;
                        }
                        if(l2==null){
                            tmp.next=l1;
                            break;
                        }
                        if(l1.val<l2.val){
                            tmp.next=l1;
                            l1=l1.next;
                            tmp=tmp.next;
                        }
                        else{
                            tmp.next=l2;
                            l2=l2.next;
                            tmp=tmp.next;
                        }
                    }
                    head=head.next;
                    lists.add(head);
                    lists.remove(0);
                    lists.remove(0);
                }
            }
            return lists.get(0);
        }

Log in to reply
 

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