Merge Two Sorted Lists Solution Explained – Step-by-Step

Data Structures / Linked List

Merge Two Sorted Lists

Easy

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

Example

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Input: list1 = [], list2 = []
Output: []

Input: list1 = [], list2 = [0]
Output: [0]

Explanation

The key insight is that both lists are already sorted. We can compare the nodes from both lists one at a time and build a new sorted list by always picking the smaller node.

We use a dummy node technique to simplify the code. The dummy node serves as the starting point of our merged list, and we maintain a current pointer that always points to the last node in our merged list.

At each step, we compare the current nodes of both lists:

If list1.val < list2.val, attach list1's node to current and move list1 forward
Otherwise, attach list2's node to current and move list2 forward
Move current pointer to the newly attached node
After one list is exhausted, attach the remaining nodes from the other list

Idea Map

Start

Create dummy node and current pointer

While list1 AND list2 exist

If list1.val < list2.val
  current.next = list1
  list1 = list1.next
Else
  current.next = list2
  list2 = list2.next
current = current.next

Attach remaining non-null list
current.next = list1 or list2

Return dummy.next

Complexity Analysis

Time Complexity

O(n + m) - We traverse each node exactly once, where n and m are the lengths of the two lists.

Space Complexity

O(1) - We only use a constant amount of extra space for pointers (dummy and current).

Code


# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
Constructor for ListNode class that initializes a node with a value and optional next pointer.
        self.val = val
Stores the value of the node.
        self.next = next
Stores reference to the next node in the list.

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
Function that takes two sorted linked lists and returns a merged sorted list.
        dummy = ListNode(0)
Creates a dummy node to serve as the starting point of our merged list - simplifies edge cases.
        current = dummy
Pointer that tracks the last node in our merged list.

        while list1 and list2:
Continue looping as long as both lists have nodes remaining.
            if list1.val < list2.val:
Compare values: if list1's current node is smaller.
                current.next = list1
Attach list1's node to our merged list.
                list1 = list1.next
Move list1 pointer to the next node.
            else:
If list2's node is smaller or equal.
                current.next = list2
Attach list2's node to our merged list.
                list2 = list2.next
Move list2 pointer to the next node.
            current = current.next
Move current pointer to the newly attached node.

        current.next = list1 if list1 else list2
Attach any remaining nodes from whichever list still has nodes.
        return dummy.next
Return the merged list, skipping the dummy node (dummy.next is the actual head).


// Definition for singly-linked list.
public class ListNode {
    int val;
Stores the value of the node.
    ListNode next;
Reference to the next node in the list.
    ListNode(int val) { this.val = val; }
Constructor that initializes a node with the given value.
}

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
Function that takes two sorted linked lists and returns a merged sorted list.
        ListNode dummy = new ListNode(0);
Creates a dummy node to serve as the starting point - simplifies edge cases.
        ListNode current = dummy;
Pointer that tracks the last node in our merged list.

        while (list1 != null && list2 != null) {
Continue looping as long as both lists have nodes remaining.
            if (list1.val < list2.val) {
Compare values: if list1's current node is smaller.
                current.next = list1;
Attach list1's node to our merged list.
                list1 = list1.next;
Move list1 pointer to the next node.
            } else {
If list2's node is smaller or equal.
                current.next = list2;
Attach list2's node to our merged list.
                list2 = list2.next;
Move list2 pointer to the next node.
            }
End of if-else statement.
            current = current.next;
Move current pointer to the newly attached node.
        }
End of while loop.

        current.next = (list1 != null) ? list1 : list2;
Attach any remaining nodes from whichever list still has nodes.
        return dummy.next;
Return the merged list, skipping the dummy node.
    }
End of function.
}


// Definition for singly-linked list.
struct ListNode {
    int val;
Stores the value of the node.
    ListNode *next;
Pointer to the next node in the list.
    ListNode(int x) : val(x), next(nullptr) {}
Constructor that initializes value and sets next to nullptr.
};

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
Function that takes two sorted linked list pointers and returns a merged sorted list pointer.
        ListNode* dummy = new ListNode(0);
Creates a dummy node to serve as the starting point - simplifies edge cases.
        ListNode* current = dummy;
Pointer that tracks the last node in our merged list.

        while (list1 != nullptr && list2 != nullptr) {
Continue looping as long as both lists have nodes remaining.
            if (list1->val < list2->val) {
Compare values: if list1's current node is smaller.
                current->next = list1;
Attach list1's node to our merged list.
                list1 = list1->next;
Move list1 pointer to the next node.
            } else {
If list2's node is smaller or equal.
                current->next = list2;
Attach list2's node to our merged list.
                list2 = list2->next;
Move list2 pointer to the next node.
            }
End of if-else statement.
            current = current->next;
Move current pointer to the newly attached node.
        }
End of while loop.

        current->next = list1 ? list1 : list2;
Attach any remaining nodes from whichever list still has nodes.
        return dummy->next;
Return the merged list, skipping the dummy node.
    }
End of function.
};

Edge Cases & Common Mistakes

⚠️

Forgetting to advance current pointer

Always remember to move current = current.next after attaching a node, otherwise you'll overwrite the same node.

💡

One or both lists are empty

The dummy node pattern handles this elegantly - just attach the non-null (or empty) list at the end.

✓

Why use a dummy node?

Without dummy, you'd need special handling for the first node. With dummy, the first node is treated like any other node.

What is Merge Sort?

Merge sort is a divide-and-conquer algorithm that splits the input in half, recursively sorts each half, and then merges the two sorted halves. This problem is essentially the merge step of merge sort!

Learn more about merge algorithms →

lightbulb

Disclaimer: This problem is for educational purposes. Practice the 'Merge Two Sorted Lists' problem on LeetCode.

AlgoExplained.dev