Java  

Merge Two Sorted Linked Lists – Step-by-Step Guide

🧩 What is a Linked List?

A linked list is a linear data structure consisting of nodes, where each node has two parts:

  • Data: The actual value stored in the node.
  • Pointer (next): A reference to the next node in the sequence.

A sorted linked list means that its elements are arranged in order (usually ascending). Linked lists are dynamic and can easily grow or shrink, unlike arrays.

Example

[1 | next] → [3 | next] → [5 | null]

📜 Problem Statement

You are given two sorted linked lists, and you must merge them into a single sorted linked list without using extra space for another data structure.

Example

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

The merged list must maintain the sorted order.

🐌 Iterative Approach

We use a dummy node as the starting point to build the new list by comparing nodes from both lists.

Steps

  1. Create a dummy node to simplify handling of the head pointer.
  2. Use a tail pointer to track the end of the merged list.
  3. Compare the values of the current nodes in both lists.
  4. Attach the smaller node to the tail and move forward in that list.
  5. Continue the process until one list is completely traversed.
  6. Attach the remaining nodes from the non-empty list to the tail.
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

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

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

    if (l1 != null) tail.next = l1;
    if (l2 != null) tail.next = l2;

    return dummy.next;
}
  • Time Complexity: O(n + m)
  • Space Complexity: O(1)

🔄 Recursive Approach

We use recursion to merge by picking the smaller head node and linking it to the merge of the rest of the lists.

Steps

  1. Base Case: If one list is null, return the other list.
  2. Compare the first nodes of both lists.
  3. Select the smaller node and recursively merge it with the remaining list.
  4. Return the smaller node as the head of the merged list.
public ListNode mergeTwoListsRecursive(ListNode l1, ListNode l2) {
    if (l1 == null) return l2;
    if (l2 == null) return l1;

    if (l1.val < l2.val) {
        l1.next = mergeTwoListsRecursive(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoListsRecursive(l1, l2.next);
        return l2;
    }
}
  • Time Complexity: O(n + m)
  • Space Complexity: O(n + m) - Due to the recursion call stack.

🧠 Why Merging Sorted Linked Lists is Important

  • Merge sort algorithm for linked lists.
  • Common technical interview question.
  • Helps understand pointer manipulation and recursive thinking.

📚 Summary

Merge two sorted linked lists efficiently.

  • What linked lists are and how they store data.
  • The problem of merging two sorted lists into one.
  • An iterative approach using a dummy node for easy pointer management.
  • A recursive approach for a cleaner, more functional style.
  • The importance of this operation in algorithms and coding interviews.

Mastering this problem will not only improve your understanding of linked lists but also help you develop skills in pointer manipulation, recursion, and algorithm design.

Membership not found