Merge Two Sorted Lists

The problem Merge Two Sorted Lists on LeetCode involves merging two sorted linked lists into a single sorted linked list. It’s a common problem that tests your understanding of linked lists and basic merging algorithms.

Problem Statement: Merge two sorted linked lists, l1 and l2, into a new sorted linked list and return its head. A sorted linked list is a linked list in which the nodes are arranged in ascending order based on their values.

l1: 1 -> 2 -> 4
l2: 1 -> 3 -> 4
merged: 1 -> 1 -> 2 -> 3 -> 4 -> 4

There are two common approaches:

• Iterative approach with two pointers: It uses two pointers to traverse the lists, compares elements, and constructs a new sorted linked list. This approach has a time complexity of $O(n + m)$ and space complexity of $O(1)$, making it efficient for most cases.
• Recursive approach: You could design a recursive solution that breaks down the lists further, merges sub-lists, and combines them. While functionally achieving the same sorted result, this approach might have a slightly higher overhead due to function calls and could potentially lead to stack overflow errors for very large lists.

Iterative approach using Swift

public class ListNode {
  public var val: Int
  public var next: ListNode?
  public init(_ val: Int) {
    self.val = val
    self.next = nil
  }
}

func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
  // Create a dummy node for the merged list
  let dummy = ListNode(0)
  var current = dummy

  // Two pointers to iterate through list1 and list2
  var l1 = list1
  var l2 = list2

  // Iterate while both lists have elements
  while l1 != nil && l2 != nil {
    // Compare values and add the smaller node to the merged list
    if l1!.val < l2!.val {
      current.next = l1
      l1 = l1!.next
    } else {
      current.next = l2
      l2 = l2!.next
    }
    current = current.next!
  }

  // Append remaining elements from either list
  current.next = l1 ?? l2

  // Return the head of the merged list (dummy.next)
  return dummy.next
}