How do you solve Merge Two Sorted Lists on LeetCode?

Merge Two Sorted Lists (LeetCode #21) can be solved using Brute Force or Optimal Solution (Two Pointers). The optimal approach is Optimal Solution (Two Pointers) with O(n) time complexity and O(1) space complexity. Key insight: Using two pointers allows for efficient merging of sorted lists without additional space.

What is the brute force solution for Merge Two Sorted Lists?

The brute force approach for Merge Two Sorted Lists is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves creating a new list by comparing each element of both lists and adding the smaller one to the new list. This is straightforward but inefficient as it requires multiple passes through the lists. The optimal Optimal Solution (Two Pointers) approach improves this to O(n).

What algorithm or data structure is used to solve Merge Two Sorted Lists?

Merge Two Sorted Lists uses the following concepts: Linked List, Recursion. The recommended patterns to study are: Two Pointers, Linked List, Merging.

What are the interview tips for Merge Two Sorted Lists?

When you first see this problem, clarify whether the input lists are guaranteed to be sorted. Communicate your approach clearly, mentioning that you will use two pointers to merge the lists efficiently. Mention edge cases such as both lists being empty or one being empty while the other has elements.

What are common mistakes when solving Merge Two Sorted Lists?

Students often forget to handle cases where one of the lists is empty. Another common mistake is not properly linking the last node of the merged list to the remaining nodes of the non-exhausted list.

#21

Merge Two Sorted Lists

Easy

Linked ListRecursionTwo PointersLinked ListMerging

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution (Two Pointers)★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal approach uses two pointers to traverse both lists simultaneously. This is efficient because we only pass through each list once, maintaining the sorted order without additional space.

⚙️

Algorithm

5 steps

1Step 1: Create a dummy node to simplify the merging process.
2Step 2: Initialize two pointers, one for each list.
3Step 3: Compare the values at the pointers and append the smaller one to the merged list, moving the corresponding pointer forward.
4Step 4: Once one list is exhausted, append the remaining nodes of the other list.
5Step 5: Return the merged list starting from the next node of the dummy.

solution.py19 lines

1# Full working Python code with comments
2class ListNode:
3    def __init__(self, val=0, next=None):
4        self.val = val
5        self.next = next
6
7def mergeTwoLists(list1, list2):
8    dummy = ListNode()
9    current = dummy
10    while list1 and list2:
11        if list1.val < list2.val:
12            current.next = list1
13            list1 = list1.next
14        else:
15            current.next = list2
16            list2 = list2.next
17        current = current.next
18    current.next = list1 if list1 else list2
19    return dummy.next

ℹ

Complexity note: The time complexity is O(n) because we traverse each list only once. The space complexity is O(1) since we are merging in place without using extra space.

1Using two pointers allows for efficient merging of sorted lists without additional space.
2The problem can be approached iteratively or recursively, but the iterative method is generally more efficient in terms of space.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.