iOS Interview - Leetcode 21. Merge Two Sorted Lists

April 30, 20242 min read#swift, #interview, #leetcode

Leetcode: 21. Merge Two Sorted Lists

  • Primary idea: Dummy Node to traverse two lists, compare two nodes and point to the right one
  • Time Complexity: O(n)
  • Space Complexity: O(1)
public class ListNode {
    public var val: Int
    public var next: ListNode?
    public init() { self.val = 0; self.next = nil; }
    public init(_ val: Int) { self.val = val; self.next = nil; }
    public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
    public func print() {
        var node: ListNode? = self
        var result = ""
        while node != nil {
            result += "\(node!.val)"
            node = node?.next
            if node != nil {
                result += " -> "
            }
        }
        Swift.print(result)
    }
}

func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
    // Initialise with a dummy node
    let headNode = ListNode(0)

    // Use another variable to manipulate the result list.
    // The headNode will be used to print the result later.
    var node = headNode

    var l1 = list1
    var l2 = list2

    while l1 != nil && l2 != nil {
        // Compare the elements of 2 lists, and point the result list to the correct one
        if l1!.val < l2!.val {
            node.next = l1
            l1 = l1!.next
        } else {
            node.next = l2
            l2 = l2!.next
        }

        // Move the pointer of the result list to the next node to prepare for the next iteration
        node = node.next!
    }

    node.next = l1 ?? l2

    return headNode.next
}

var list11 = ListNode(1)
var list12 = ListNode(2)
var list13 = ListNode(4)
list11.next = list12
list12.next = list13
list11.print() // 1 -> 2 -> 4

var list21 = ListNode(1)
var list22 = ListNode(3)
var list23 = ListNode(4)
list21.next = list22
list22.next = list23
list21.print() // 1 -> 3 -> 4

let result = mergeTwoLists(list11, list21)
result?.print() // 1 -> 1 -> 2 -> 3 -> 4 -> 4
Quick Drop logo

Profile picture

Personal blog by An Tran. I'm focusing on creating useful apps.
#Swift #Kotlin #Mobile #MachineLearning #Minimalist


© An Tran - 2024