0023 - Merge k Sorted Lists (Hard)

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Input: lists = []
Output: []

Input: lists = [[]]
Output: []

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode *mergeKLists(vector<ListNode*> &lists) {
        if (lists.size() == 0) return nullptr;
        while (lists.size() > 1) {
            vector<ListNode *> nlists;
            for (int i = 0; i < lists.size(); i += 2) {
                ListNode* l = lists[i];
                ListNode* r = i + 1 < lists.size() ? lists[i + 1] : nullptr;
                ListNode* merged = mergeTwoLists(l, r);
                nlists.push_back(merged);
            }
            lists = nlists;
        }
        return lists[0];
    }

    // Solution from 0021 - Merge Two Sorted Lists (Easy)
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (list1 == nullptr) return list2;
        else if (list2 == nullptr) return list1;
        else if (list1->val < list2->val) {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        } else {
            list2->next = mergeTwoLists(list2->next, list1);
            return list2;
        }
    }
};

/**
 * 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) {
        int len = lists.length;
        if (len == 0) {
            return null;
        }

        return mergeKLists(lists, 0, len - 1);
    }

    public ListNode mergeKLists(ListNode[] lists, int start, int end) {
        if (end - start == 0) {
            return lists[start];
        }
        if (end - start == 1) {
            return mergeLists(lists[start], lists[end]);
        }
        int mid = start + ((end - start) / 2);
        ListNode listA = mergeKLists(lists, start, mid);
        ListNode listB = mergeKLists(lists, mid + 1, end);
        return mergeLists(listA, listB);
    }

    public ListNode mergeLists(ListNode listA, ListNode listB) {
        if (listA == null) {
            return listB;
        }
        if (listB == null) {
            return listA;
        }
        if (listA.val < listB.val) {
            listA.next = mergeLists(listA.next, listB);
            return listA;
        } else {
            listB.next = mergeLists(listA, listB.next);
            return listB;
        }
    }
}

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        # edgecases: if length is 0 and lists is None
        if not lists or len(lists) == 0:
            return None
        # take pairs of LL and merge them each time and
        # keep doing it until there is one LL remaining
        while len(lists) > 1:
            merged_lists = []
            # iterate through each of these lists
            for i in range(0, len(lists), 2):
                l1 = lists[i]
                # make sure if i + 1 is in bounds because l2 might be out of bound
                # maybe we can have odd number of lists
                l2 = lists[i + 1] if (i + 1) < len(lists) else None
                # merge them together and add to merged lists
                merged_lists.append(self.mergeLists(l1, l2))
            # update lists variable
            lists = merged_lists
            # keep doing that until there is one list
        return lists[0]

    # solution from 0021 - Merge Two Sorted Lists (Easy)
    def mergeLists(self, l1, l2):
        dymmy = ListNode()
        tail = dymmy

        while l1 and l2:
            if l1.val < l2.val:
                tail.next = l1
                l1 = l1.next
            else:
                tail.next = l2
                l2 = l2.next
            tail = tail.next

        if l1:
            tail.next = l1
        elif l2:
            tail.next = l2

        return dymmy.next

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function (lists) {
  if (!lists || lists.length == 0) return null;
  while (lists.length > 1) {
    let merged_lists = [];
    for (i = 0; i < lists.length; i += 2) {
      let l1 = lists[i];
      let l2 = i + 1 < lists.length ? lists[i + 1] : null;
      merged_lists.push(merge(l1, l2));
    }
    lists = merged_lists;
  }
  return lists[0];
};

var merge = function (l1, l2) {
  dummy = new ListNode();
  tail = dummy;
  while (l1 && l2) {
    if (l1.val < l2.val) {
      tail.next = l1;
      l1 = l1.next;
    } else {
      tail.next = l2;
      l2 = l2.next;
    }
    tail = tail.next;
  }
  if (l1) tail.next = l1;
  if (l2) tail.next = l2;
  return dummy.next;
};