Problem Statement

You are given the heads of two sorted linked lists list1 and list2.
…
Return the head of the merged linked list.

Merge Two Sorted Lists - LeetCode

Approach

  1. Create a new node. next of this node will be the head of the merged list.
  2. Create a pointer current that keeps track of the last node in the merged list.
  3. While both lists are not empty:
    1. Identify the smaller element between the two lists.
    2. Set current to this smaller element.
    3. Move it’s list pointer to the next element.
    4. Set current to it’s next element.
  4. If one of the lists is not empty, set the next of current to the remaining list.

Solution in Swift

/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
class Solution {
    func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
        var one = list1
        var two = list2
        let result = ListNode()
        var current = result
        
        while one != nil && two != nil {
            if one!.val < two!.val {
                current.next = one
                one = one!.next
            } else {
                current.next = two
                two = two!.next
            }
            current = current.next!
        }
        
        if one != nil {
            current.next = one
        } else {
            current.next = two
        }
        return result.next
    }
}

Complexity

  • Time complexity: \(O(n + m)\), where \(n\) and \(m\) are the number of elements in the two lists.
  • Space complexity: \(O(1)\)