Data Structures and Algorithms (DSA)  

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:

  1. Create a dummy node (to simplify logic)

  2. Use a current pointer starting from dummy

  3. Compare values of both list nodes

  4. Attach the smaller node to current

  5. Move the pointer of the chosen list

  6. Continue until one list ends

  7. Attach the remaining part of the other list

Dry Run Example

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

CurrentList1List2Action
dummy12pick 1
132pick 2
234pick 3
354pick 4
456pick 5
5null6attach 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.

Membership not found