Merge k Sorted Lists

mergeKLists.java

/*
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Algorithm:
1. Needs a dummy node that helps to insert a node at the beginning of the list.
2. Use devise and conquer algorithm
  a. Keep one list to be return.
  b. Continue to merge other lists to the list to be return.

*/
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(lists.size() == 0) return null;
        ListNode dummy = new ListNode(0);
        dummy.next = lists.get(0);
        for(int i = 1; i < lists.size(); i++) {
            merge2List(dummy, lists.get(i));
        }
        return dummy.next;
    }
    
    public void merge2List(ListNode dummy, ListNode node) {
        ListNode walker = dummy.next;
        ListNode prev = dummy;
        if(walker == null) {
            dummy.next = node;
        }
        while(walker != null && node != null) {
            if(walker.val < node.val) {
                if(walker.next == null) {
                    walker.next = node;
                    break;
                } else {
                    prev = walker; // change the pointer to point walker
                    walker = walker.next;
                }
            } else if(walker.val >= node.val) {
                // insert node into walker
                ListNode tmp = node.next;
                prev.next = node;
                prev = node; // update the prev
                node.next = walker;
                node = tmp; // change it back to next linkedlist
            }
        }
    }
}