A simple java solution using iteration


  • 0

    Below is my simple solution using only iteration. First loop decides distance of two comparing lists, and second one decides started list. After each merging, result list is kept in the started list index. Therefore final result is in lists[0].

    public class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            if(lists.length < 1) return null;
            int len = lists.length;
            for(int i = 1; i < len; i = 2*i){
                for(int j = 0; j+i < len; j = j+2*i){
                    ListNode a = lists[j];
                    ListNode b = lists[j+i];
                    ListNode head = new ListNode(0);
                    ListNode cur = head;
                    while(a != null && b != null){
                        ListNode c;
                        if(a.val > b.val){
                            c = b;
                            b = b.next;
                        }else{
                            c = a;
                            a = a.next;
                        }
                        cur.next = c;
                        cur = cur.next;
                    }
                    cur.next = (a != null) ? a : b;
                    lists[j] = head.next;
                }
            }
            return lists[0];
        }
    }
    

Log in to reply
 

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