DSA

Merge Two Sorted Lists

Covers: Using dummy node, Approach2: Recursive Merge. Optimal — Time O(m+n), Space O(m+n).

August 8, 2026

DSA Linked List LeetCode Practice Sorting Two Pointers

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Approach 1: Using dummy node#

Analogy: Like zipping two sorted queues together by always taking the smallest front element.

Create a dummy sentinel node and maintain a tail pointer into the merged list. At each step compare the heads of the two lists, attach the smaller node to tail->next, and advance that list's pointer. When one list is exhausted, append the remainder of the other. Return dummy->next. The dummy node eliminates the edge case of handling an empty merged list separately. Space is O(1) since nodes are re-linked in place.

cpp

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        
        ListNode* newHead = new ListNode(-1);
        ListNode* tail = newHead;

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

        if(list1)
            tail->next = list1;
        if(list2)
            tail->next = list2;

        return newHead->next;
    }
};

Time Complexity: O(m+n)

Space Complexity: O(1)

Approach2: Recursive Merge#

Analogy: Merge the smallest head first and let recursion handle the rest.

At each call, pick the node with the smaller value as the head of the merged list and set its next to the recursive result of merging the remaining part of that list with the full other list. Base cases handle when either list is null. This is elegant but uses O(m+n) stack space for the recursion depth — the trade-off compared to the iterative dummy-node approach.

cpp

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        
        if(!list1)
            return list2;
        if(!list2)
            return list1;

        if(list1->val < list2->val){
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }else{
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
            
    }
};

Time Complexity: O(m+n)

Space Complexity: O(m+n)

DSARotate ListCovers: Naive, Optimal (circular link). Optimal — Time O(n), Space O(1).DSAMerge k Sorted ListsCovers: Brute Force, Optimal. Optimal — Time O(N).DSAMerge Two Sorted ArraysCovers: Extra Space (Naive), Two Pointers from End (Optim…, Gap Method (Shell Sort idea). Optimal — Space O(m + n).

Approach 1: Using dummy node#

Approach2: Recursive Merge#

Related articles