【Hot100】23. Merge K ascending linked lists

23. Merge K An ascending list
Difficult questions
Here's an array of linked lists , Each list has been listed in ascending order .
Please merge all the linked lists into one ascending list , Return the merged linked list .

Ideas ： Merge two linked lists one by one

First of all, review 【Hot100】21. Merge two ordered lists

The following are posted 「merge2Lists」 Of 「 recursive 」 and 「 iteration 」 Two implementations ：

• recursive

class Solution {
    
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    
        if (list1 == null) {
    
            return list2;
        }
        else if (list2 == null) {
    
            return list1;
        }
        else if (list1.val < list2.val) {
    
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        }
        else {
    
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }

    }
}

• iteration

private ListNode merge2Lists(ListNode l1, ListNode l2) {
    
    ListNode dummyHead = new ListNode(0);
    ListNode tail = dummyHead;
    while (l1 != null && l2 != null) {
    
        if (l1.val < l2.val) {
    
            tail.next = l1;
            l1 = l1.next;
        } else {
    
            tail.next = l2;
            l2 = l2.next;
        }
        tail = tail.next;
    }

    tail.next = l1 == null? l2: l1;

    return dummyHead.next;
}

• Merge one by one

class Solution {
    
    public ListNode mergeKLists(ListNode[] lists) {
    
        ListNode res = null;
        for (ListNode list: lists) {
    
            res = merge2Lists(res, list);
        }
        return res;
    }
}

Pair by pair 1 To optimize ：

• A merger of two - iteration

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */
class Solution {
    
    public ListNode mergeKLists(ListNode[] lists) {
    
        if (lists.length == 0) {
    
            return null;
        }
        int k = lists.length;
        while (k > 1) {
    
            int idx = 0;
            for (int i = 0; i < k; i += 2) {
    
                if (i == k - 1) {
    
                    lists[idx++] = lists[i];
                } else {
    
                    lists[idx++] = merge2Lists(lists[i], lists[i + 1]);
                }
            }
            k = idx;
        }
        return lists[0];
    }

    private ListNode merge2Lists(ListNode l1, ListNode l2) {
    
        ListNode dummyHead = new ListNode(0);
        ListNode tail = dummyHead;
        while (l1 != null && l2 != null) {
    
            if (l1.val < l2.val) {
    
                tail.next = l1;
                l1 = l1.next;
            } else {
    
                tail.next = l2;
                l2 = l2.next;
            }
            tail = tail.next;
        }

        tail.next = l1 == null? l2: l1;

        return dummyHead.next;
    }
}

• A merger of two - recursive

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */
class Solution {
    
    public ListNode mergeKLists(ListNode[] lists) {
    
        if (lists.length == 0) {
    
            return null;
        }
        return merge(lists, 0, lists.length - 1);
    }

    private ListNode merge(ListNode[] lists, int lo, int hi) {
    
        if (lo == hi) {
    
            return lists[lo];
        }
        int mid = lo + (hi - lo) / 2;
        ListNode l1 = merge(lists, lo, mid);
        ListNode l2 = merge(lists, mid + 1, hi);
        return mergeTwoLists(l1, l2);
    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    
        if (list1 == null) {
    
            return list2;
        }
        else if (list2 == null) {
    
            return list1;
        }
        else if (list1.val < list2.val) {
    
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        }
        else {
    
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }

    }
}

class Solution {
    
   public ListNode mergeKLists(ListNode[] lists) {
    
        if (lists == null || lists.length == 0) return null;
        return merge(lists, 0, lists.length - 1);
    }

    // Merge functions 
    private ListNode merge(ListNode[] lists, int left, int right) {
    
        if (left == right) return lists[left];
        int mid = left + (right - left) / 2;
        ListNode l1 = merge(lists, left, mid);
        ListNode l2 = merge(lists, mid + 1, right);
        return mergeTwoLists(l1, l2);
    }

    // Merge two ascending linked lists 
    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    
    	ListNode dummyHead = new ListNode(0);
    	ListNode cur = dummyHead;
    	while (l1 != null && l2 != null) {
    
        	if (l1.val < l2.val) {
    
            	cur.next = l1;
            	l1 = l1.next;
        	} else {
    
                cur.next = l2;
            	l2 = l2.next;
        	}
            // Move and merge the next node of the linked list 
        	cur = cur.next;
    	}
        
        // If linked list 1 It's empty , Then merge the linked list and put the linked list 2 The rest is connected at the back , Otherwise, connect the linked list 1 node 
        if(l1 == null){
    
        	cur.next = l2;
        }else{
    
        	cur.next = l1;
        }
    	//cur.next = l1 == null? l2 : l1;
    	return dummyHead.next;
	}
}