Merge Two Sorted Linked Lists – DSA Problem Explained

Introduction

The Merge Two Sorted Linked Lists problem is a very common DSA interview question, especially in linked list topics. It tests your understanding of pointers, node manipulation, and handling edge cases.

In simple words, this problem asks you to combine two already sorted linked lists into one single sorted linked list.

This article explains the problem in simple, human-friendly language, step by step, with examples and interview-ready code.

What is a Linked List?

A Linked List is a linear data structure in which elements (nodes) are connected via pointers.

Each node contains:

A data value
A pointer to the next node

Unlike arrays, linked lists do not store elements in continuous memory locations.

What Does “Sorted Linked List” Mean?

A sorted linked list means the values inside the list are already arranged in increasing order.

Example

List 1: 1 → 3 → 5

List 2: 2 → 4 → 6

Both lists are individually sorted.

Problem Statement

You are given the heads of two sorted linked lists. Your task is to merge them into a single sorted linked list and return the head of the new list.

Example

Input:
List1 = 1 → 3 → 5
List2 = 2 → 4 → 6

Output:
1 → 2 → 3 → 4 → 5 → 6

Why Brute Force is Not Ideal

A naive approach could be:

Copy all values into an array
Sort the array
Create a new linked list

Problems with This Approach

Extra space required
Sorting adds unnecessary time

Interviewers expect a pointer-based solution.

Optimized Approach Using Two Pointers

The best approach is to use two pointers, one for each linked list.

Key Idea

Compare the current nodes of both lists
Pick the smaller value
Move the pointer forward

This keeps the list sorted without extra space.

Step-by-Step Explanation

Steps:

Create a dummy node (to simplify logic)
Use a current pointer starting from dummy
Compare values of both list nodes
Attach the smaller node to current
Move the pointer of the chosen list
Continue until one list ends
Attach the remaining part of the other list

Dry Run Example

List1: 1 → 3 → 5
List2: 2 → 4 → 6

Current	List1	List2	Action
dummy	1	2	pick 1
1	3	2	pick 2
2	3	4	pick 3
3	5	4	pick 4
4	5	6	pick 5
5	null	6	attach rest

Final List: 1 → 2 → 3 → 4 → 5 → 6

Iterative Code Implementation

C++ Code

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* current = &dummy;

    while (l1 && l2) {
        if (l1->val < l2->val) {
            current->next = l1;
            l1 = l1->next;
        } else {
            current->next = l2;
            l2 = l2->next;
        }
        current = current->next;
    }

    current->next = l1 ? l1 : l2;
    return dummy.next;
}

Java Code

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;

    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }

    current.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

Python Code

def mergeTwoLists(l1, l2):
    dummy = ListNode(0)
    current = dummy

    while l1 and l2:
        if l1.val < l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next

    current.next = l1 if l1 else l2
    return dummy.next

Recursive Approach (Also Important)

Idea

Compare heads
Recursively merge remaining lists

C++ Recursive Code

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (!l1) return l2;
    if (!l2) return l1;

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

Time and Space Complexity

Time Complexity: O(n + m)
Space Complexity:
- Iterative: O(1)
- Recursive: O(n + m) (recursion stack)

Important Edge Cases

One list is empty
Both lists are empty
Lists contain duplicate values

These cases are often checked in interviews.

Common Interview Follow-Up Questions

Merge K sorted linked lists
Merge linked lists without extra space
Difference between iterative and recursive approaches

Summary

The Merge Two Sorted Linked Lists problem is a fundamental linked list question that tests pointer manipulation skills. By using a two-pointer technique, you can merge lists efficiently without using extra space. Understanding both iterative and recursive approaches, along with edge cases, will help you confidently solve linked list problems in technical interviews.