23. Merge k Sorted Lists

https://leetcode.com/problems/merge-k-sorted-lists/

C++

/**
 * 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.empty()) {
            return nullptr;
        }
        return mergeHelper(lists, 0, lists.size() - 1);
    }

    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* dummy = new ListNode();
        ListNode* current = dummy;
        while (list1 && list2) {
            if (list1->val <= list2->val) {
                current->next = list1;
                list1 = list1->next;
            } else {
                current->next = list2;
                list2 = list2->next;
            }
            current = current->next;
        }
        current->next = list1 ? list1 : list2;
        return dummy->next;
    }

    ListNode* mergeHelper(vector<ListNode*>& lists, int left, int right) {
        if (left == right) {
            return lists[left];
        }
        int mid = (left + right) / 2;
        ListNode* list1 = mergeHelper(lists, left, mid);
        ListNode* list2 = mergeHelper(lists, mid + 1, right);
        return mergeTwoLists(list1, list2);
    }
};

Go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeKLists(lists []*ListNode) *ListNode {
  if len(lists) == 0 {
    return nil
  }
  return mergeHelper(lists, 0, len(lists)-1)
}

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
  dummy := new(ListNode)
  current := dummy

  for list1 != nil && list2 != nil {
    if list1.Val <= list2.Val {
      current.Next = list1
      list1 = list1.Next
    } else {
      current.Next = list2
      list2 = list2.Next
    }
    current = current.Next
  }

  if list1 != nil {
    current.Next = list1
  } else {
    current.Next = list2
  }

  return dummy.Next
}

func mergeHelper(lists []*ListNode, left int, right int) *ListNode {
  if left == right {
    return lists[left]
  }
  mid := (left + right) / 2
  list1 := mergeHelper(lists, left, mid)
  list2 := mergeHelper(lists, mid+1, right)
  return mergeTwoLists(list1, list2)
}

JavaScript

/**
 * 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.length === 0) {
    return null
  }
  return mergeHelper(lists, 0, lists.length - 1)
};

function mergeTwoLists(list1, list2) {
  const dummy = new ListNode()
  let current = dummy
  while (list1 && list2) {
    if (list1.val <= list2.val) {
      current.next = list1
      list1 = list1.next
    } else {
      current.next = list2
      list2 = list2.next
    }
    current = current.next
  }
  current.next = list1 || list2
  return dummy.next
}

function mergeHelper(lists, left, right) {
  if (left === right) {
    return lists[left]
  }
  const mid = (left + right) / 2 >> 0
  const list1 = mergeHelper(lists, left, mid)
  const list2 = mergeHelper(lists, mid + 1, right)
  return mergeTwoLists(list1, list2)
}

Python

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[Optional[ListNode]]
        :rtype: Optional[ListNode]
        """
        if not lists:
            return None
        return self.mergeHelper(lists, 0, len(lists) - 1)

    def mergeTwoLists(self, list1, list2):
        current = dummy = ListNode()
        while list1 and list2:
            if list1.val <= list2.val:
                current.next = list1
                list1 = list1.next
            else:
                current.next = list2
                list2 = list2.next
            current = current.next
        current.next = list1 if list1 else list2
        return dummy.next

    def mergeHelper(self, lists, left, right):
        if left == right:
            return lists[left]
        mid = (left + right) // 2
        list1 = self.mergeHelper(lists, left, mid)
        list2 = self.mergeHelper(lists, mid + 1, right)
        return self.mergeTwoLists(list1, list2)