21. Merge Two Sorted Lists - Leetcode Solution

LeetCode problem

Solution code

💡 Step-by-Step Thought Process

Understand the problem: Merge two sorted linked lists into one sorted linked list.
Create a dummy node to serve as the starting point of the merged list.
Initialize a current pointer to the dummy node to build the merged list.
While both list1 and list2 have nodes, compare the values of their current nodes.
If list1's value is less than list2's value, attach list1's node to the current pointer, move current to list1's node, and advance list1 to its next node.
Otherwise, attach list2's node to the current pointer, move current to list2's node, and advance list2 to its next node.
After the loop, attach any remaining nodes from list1 or list2 to the current pointer.
Return the next node of the dummy node as the head of the merged list.

Code Solution

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        d = ListNode()
        cur = d

        while list1 and list2:
            if list1.val < list2.val:
                cur.next = list1
                cur = list1
                list1 = list1.next
            else:
                cur.next = list2
                cur = list2
                list2 = list2.next

        cur.next = list1 if list1 else list2

        return d.next

# Time Complexity: O(n)
# Space Complexity: O(1)

#include <iostream>
using namespace std;


class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode dummy(0);
        ListNode* cur = &dummy;

        while (list1 && list2) {
            if (list1->val < list2->val) {
                cur->next = list1;
                list1 = list1->next;
            } else {
                cur->next = list2;
                list2 = list2->next;
            }
            cur = cur->next;
        }

        cur->next = list1 ? list1 : list2;

        return dummy.next;
    }
};

public class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;

        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                cur.next = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }

        cur.next = list1 != null ? list1 : list2;

        return dummy.next;
    }
}

var mergeTwoLists = function(list1, list2) {
    let dummy = new ListNode(0);
    let cur = dummy;

    while (list1 !== null && list2 !== null) {
        if (list1.val < list2.val) {
            cur.next = list1;
            list1 = list1.next;
        } else {
            cur.next = list2;
            list2 = list2.next;
        }
        cur = cur.next;
    }

    cur.next = list1 !== null ? list1 : list2;

    return dummy.next;
};

Detailed Explanation

Understanding the Problem: Merge Two Sorted Lists

The “Merge Two Sorted Lists” problem asks us to merge two sorted singly linked lists, list1 and list2, into one new sorted linked list. The goal is to preserve the non-decreasing order of elements and return the head of the newly merged list.

Example:

Input: list1 = 1 → 2 → 4, list2 = 1 → 3 → 4
Output: 1 → 1 → 2 → 3 → 4 → 4

Why This Problem Matters

Merging two sorted lists is a foundational concept used in algorithms such as merge sort and in real-world scenarios involving sorted streams of data. It reinforces pointer manipulation in linked lists and teaches how to maintain sorted order efficiently.

Optimal Approach: Iterative Merge with a Dummy Node

The most effective way to merge two sorted lists is to use a dummy node to simplify edge cases and a current pointer to build the merged list incrementally.

Steps:

Create a dummy node that will serve as the placeholder for the merged list.
Initialize a current pointer pointing to the dummy node.
While both list1 and list2 are non-null:
- Compare the values of list1 and list2.
- Attach the node with the smaller value to current.next.
- Move current forward and also advance the list from which the node was taken.
After the loop, at most one list will have nodes remaining. Attach the remaining nodes to current.next.
Return dummy.next as the head of the merged list.

Example Walkthrough

Inputs: list1 = 1 → 2 → 4, list2 = 1 → 3 → 4
Execution:

Compare 1 and 1 → pick either → attach to merged list
Compare 2 and 1 → pick 1 from list2
Compare 2 and 3 → pick 2
Compare 4 and 3 → pick 3
Compare 4 and 4 → pick either
Remaining node 4 → attach

Result: 1 → 1 → 2 → 3 → 4 → 4

Time and Space Complexity

Time Complexity: O(n + m), where n is the length of list1 and m is the length of list2. Each node is visited exactly once.
Space Complexity: O(1) auxiliary space, since we are not creating any new nodes (just reusing and rearranging pointers).

Edge Cases to Consider

One or both lists are empty → return the non-empty list or null
Lists with all duplicate values → handled correctly
One list is significantly longer than the other → still works in linear time

Conclusion

The “Merge Two Sorted Lists” problem is a classic example of how to manipulate linked lists efficiently using pointers. By reusing existing nodes and carefully adjusting links, we can produce a clean, sorted list with no additional space. This problem forms the backbone of more complex algorithms and teaches critical low-level manipulation skills.

NEW!Need help landing software roles? 💡

AlgoMap.io