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.

```
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
}
```

Polynomial Rolling HashJun 06, 2024

Big-O NotationFeb 06, 2024

Rabin–Karp String SearchingSep 10, 2021

Dynamic Programming (DP)Jan 16, 2022

Competitive Programming TopicsFeb 02, 2022

Bloom FilterFeb 02, 2022

Data Structures Used in Competitive ProgrammingFeb 04, 2022