23. Merge k Sorted Lists

Posted on | In |
  • Source : Link
  • Author : Han
  • Date : 2022-02-16

Problems

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
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

Example 2:

1
2
3
Input: lists = []
Output: []

Example 3:

1
2
Input: lists = [[]]
Output: []

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun mergeKLists(lists: Array<ListNode?>): ListNode? {
        return when {
            lists.size == 1 -> lists.first()
            lists.isEmpty() -> null
            else -> lists.reduce { originalNode, nextNode -> merge(originalNode, nextNode) }
        }
    }

    private fun merge(originalNode: ListNode?, nextNode: ListNode?): ListNode? {
        return when {
            originalNode == null || nextNode == null -> originalNode ?: nextNode
            originalNode.`val` < nextNode.`val` -> {
                originalNode.next = this.merge(originalNode.next, nextNode)
                originalNode
            }
            else -> {
                nextNode.next = this.merge(originalNode, nextNode.next)
                nextNode
            }
        }
    }
}