LeetCode: 23. Merge k Sorted Lists

LeetCode: 23. Merge k Sorted Lists

Problem: 23. Merge k Sorted Lists

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

Difficulty: Hard

Description:

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

Example:

Input:

[
1->4->5,
1->3->4,
2->6
]

Output: 1->1->2->3->4->4->5->6

Solution:

Language: Swift

Runtime: 116ms
Memory: 25.3MB

Copy to Clipboard

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.next = nil
 *     }
 * }
 */
class Solution {
    func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
        if lists.isEmpty {
            return nil
        }
        if lists.count == 1 {
            return lists[0]
        }
        
        let middle = lists.count / 2
        let left = mergeKLists(Array(lists[0 ..< middle]))
        let right = mergeKLists(Array(lists[middle...]))
        
        return mergeTwoLists(left, right)
    }
    
    func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        if l1 == nil {
            return l2
        }
        if l2 == nil {
            return l1
        }
        
        if l1!.val < l2!.val {
            l1!.next = mergeTwoLists(l1!.next, l2)
            return l1
        } else {
            l2!.next = mergeTwoLists(l2!.next, l1)
            return l2
        }
        return nil
    }
}

Related Posts

Leave A Comment Cancel reply