Merge Two Sorted Linked Lists in DSA Java - Deep Dive

Overview - Merge Two Sorted Linked Lists

What is it?

Merging two sorted linked lists means combining them into one new linked list that is also sorted. Each input list is already in order, and the goal is to create a single list that keeps this order. This process involves comparing elements from both lists step-by-step and linking them in sorted order. It is a common operation in many algorithms and data processing tasks.

Why it matters

Without merging sorted lists efficiently, programs would waste time sorting data repeatedly or lose the order that makes searching and processing faster. Merging helps keep data organized and speeds up tasks like combining search results or processing streams of information. If this concept didn't exist, many applications would be slower and more complex.

Where it fits

Before learning this, you should understand what linked lists are and how to traverse them. After mastering merging, you can explore sorting algorithms like merge sort, which uses this merging step repeatedly. This topic fits in the middle of learning linked lists and sorting techniques.

Mental Model

Core Idea

Merging two sorted linked lists means walking through both lists together, always picking the smaller current element to build a new sorted list.

Think of it like...

Imagine two friends lining up in order of height to enter a room. You let them in one by one, always choosing the shorter person waiting at the front of either line, so the final line inside is perfectly ordered by height.

List1: 1 -> 3 -> 5 -> null
List2: 2 -> 4 -> 6 -> null

Merge process:
Start: Compare 1 and 2 -> pick 1
Next: Compare 3 and 2 -> pick 2
Next: Compare 3 and 4 -> pick 3
Next: Compare 5 and 4 -> pick 4
Next: Compare 5 and 6 -> pick 5
Next: Only 6 left -> pick 6

Result: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Build-Up - 7 Steps

1

Foundation

Understanding Linked List Structure

Concept: Learn what a linked list is and how nodes connect to form a chain.

A linked list is a chain of nodes where each node holds a value and a link to the next node. The last node points to null, showing the end of the list. For example, a list with values 1, 3, 5 looks like: 1 -> 3 -> 5 -> null.

Result

You can visualize and traverse a linked list by following the next links from the first node until you reach null.

Understanding the basic structure of linked lists is essential because merging relies on moving through these links step-by-step.

2

Foundation

What Does Sorted Mean in Linked Lists

Concept: Recognize that sorted linked lists have their values in increasing order.

A sorted linked list means each node's value is less than or equal to the next node's value. For example, 1 -> 3 -> 5 -> null is sorted, but 3 -> 1 -> 5 -> null is not. This order allows efficient merging by comparing only the front nodes of each list.

Result

Knowing the lists are sorted lets us merge by simple comparisons without scanning entire lists repeatedly.

Knowing the input lists are sorted simplifies the merging process and avoids extra sorting steps.

3

Intermediate

Step-by-Step Merging Process

🤔Before reading on: do you think we should compare all nodes at once or just the current nodes at the front of each list? Commit to your answer.

Concept: Merge by comparing only the current nodes at the front of each list and choosing the smaller one to add next.

Start with two pointers, one at the head of each list. Compare their values. Attach the smaller node to the merged list and move that pointer forward. Repeat until one list is empty, then attach the remaining nodes from the other list.

Result

The merged list contains all nodes from both lists in sorted order without extra sorting.

Comparing only the front nodes at each step keeps the process efficient and straightforward.

4

Intermediate

Using a Dummy Node to Simplify Merging

🤔Before reading on: do you think starting the merged list with the first real node or a dummy node is easier to manage? Commit to your answer.

Concept: Use a dummy node as a starting point to avoid special cases when building the merged list.

Create a dummy node that acts as a fixed starting point. Use a pointer to build the merged list by linking nodes after the dummy. At the end, return dummy.next as the head of the merged list. This avoids checking if the merged list is empty during the process.

Result

The code becomes cleaner and easier to write without special cases for the first node.

Using a dummy node is a common technique to simplify linked list operations and reduce bugs.

5

Intermediate

Handling Remaining Nodes After One List Ends

🤔Before reading on: do you think we need to compare nodes after one list is empty? Commit to your answer.

Concept: Once one list is empty, append the remaining nodes of the other list directly.

After the main loop, one list may still have nodes left. Since the lists are sorted, these remaining nodes are already in order and can be linked directly to the merged list without further comparisons.

Result

The merged list is complete and sorted, including all nodes from both lists.

Recognizing that leftover nodes are already sorted saves unnecessary work and keeps the algorithm efficient.

6

Advanced

Iterative vs Recursive Merging Approaches

🤔Before reading on: do you think recursion or iteration is simpler for merging linked lists? Commit to your answer.

Concept: Merging can be done using iteration with a loop or recursion by calling the function on smaller sublists.

Iterative merging uses a loop and a dummy node to build the merged list step-by-step. Recursive merging compares the heads and calls itself on the rest of the lists, building the merged list as the recursion unwinds. Both produce the same result but differ in style and memory use.

Result

Both methods produce a sorted merged list, but recursion uses more memory due to call stack, while iteration is more memory efficient.

Understanding both approaches helps choose the best one for different situations, balancing clarity and resource use.

7

Expert

In-Place Merging Without Extra Nodes

🤔Before reading on: do you think merging always requires creating new nodes? Commit to your answer.

Concept: Merge two sorted linked lists by rearranging existing nodes' links without creating new nodes or dummy nodes.

Instead of creating a new list, adjust the next pointers of the existing nodes to link them in sorted order. Keep track of the head of the merged list by comparing the first nodes. Then iterate through both lists, linking nodes from one list into the other as needed. This saves memory and is efficient.

Result

The merged list reuses original nodes, saving space and avoiding extra allocations.

Knowing how to merge in-place is crucial for memory-sensitive applications and shows mastery of pointer manipulation.

Under the Hood

Merging works by maintaining pointers to the current nodes in both lists. At each step, the algorithm compares the values at these pointers and links the smaller node to the merged list. The pointer for the chosen node advances to the next node. This continues until one list is exhausted, then the remaining nodes of the other list are linked directly. Internally, this manipulates the 'next' references of nodes to build a new chain without copying data.

Why designed this way?

This method was designed to leverage the sorted property of input lists, allowing merging in linear time without extra sorting. Using pointers and direct link manipulation avoids creating new nodes, saving memory and time. Alternatives like copying nodes or sorting combined lists are less efficient. The dummy node technique simplifies edge cases, making the code cleaner and less error-prone.

┌─────────────┐       ┌─────────────┐
│ List1 Head  │──────▶│ Node1 (val) │
└─────────────┘       └─────┬───────┘
                              │ next
                              ▼
                         ┌─────────────┐
                         │ Node2 (val) │
                         └─────┬───────┘
                               │ next
                               ▼
┌─────────────┐       ┌─────────────┐
│ List2 Head  │──────▶│ NodeA (val) │
└─────────────┘       └─────┬───────┘
                              │ next
                              ▼
                         ┌─────────────┐
                         │ NodeB (val) │
                         └─────────────┘

Merging pointers move along these nodes, linking smaller nodes into merged list.

Myth Busters - 3 Common Misconceptions

Quick: Do you think merging two sorted linked lists always requires creating new nodes? Commit to yes or no.

Common Belief: Merging means creating a brand new linked list with new nodes copying values from both lists.

Reality: Merging can be done by rearranging the existing nodes' links without creating any new nodes.

Why it matters: Creating new nodes wastes memory and time, especially with large lists. Understanding in-place merging leads to more efficient code.

Quick: Do you think the merged list can be unsorted if input lists are sorted? Commit to yes or no.

Common Belief: Merging two sorted lists might produce an unsorted list if not careful.

Reality: If merging is done correctly by always picking the smaller current node, the merged list is guaranteed to be sorted.

Why it matters: Incorrect merging logic can break sorting, causing bugs in later processing that rely on order.

Quick: Do you think recursion is always better than iteration for merging? Commit to yes or no.

Common Belief: Recursive merging is simpler and always preferred over iterative merging.

Reality: While recursion can be elegant, it uses more memory due to call stack and can cause stack overflow on large lists. Iteration is more memory efficient.

Why it matters: Choosing recursion blindly can cause crashes or inefficiency in real applications.

Expert Zone

1

When merging in-place, careful pointer updates are needed to avoid losing access to nodes, which can cause memory leaks or corrupted lists.

2

Using a dummy node is a subtle but powerful technique that simplifies code by removing special cases for the first node insertion.

3

Recursive merging can be optimized with tail recursion in some languages, but Java does not support tail call optimization, so iteration is safer.

When NOT to use

If the input lists are not sorted, this merging approach does not work correctly. Instead, you should sort the lists first or use a different method like concatenation followed by sorting. Also, if the lists are extremely large and memory is limited, iterative in-place merging is preferred over recursion to avoid stack overflow.

Production Patterns

In real systems, merging sorted linked lists is used in merge sort implementations, external sorting of large data sets, and combining sorted streams of data like logs or search results. Production code often uses iterative in-place merging with dummy nodes for clarity and efficiency.

Connections

Merge Sort Algorithm

Builds-on

Understanding how to merge two sorted lists is the key step in merge sort, which recursively splits and merges lists to sort data efficiently.

Priority Queues (Heaps)

Alternative approach

Merging multiple sorted lists can also be done using priority queues, which generalize the merging process beyond two lists and optimize for many inputs.

Real-Life Queue Management

Similar pattern

Merging sorted lists is like managing multiple queues of people ordered by arrival time, combining them into one queue while preserving order, a concept used in event scheduling and customer service.

Common Pitfalls

#1 Losing track of nodes by overwriting pointers incorrectly.

Wrong approach:

while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
list1 = list1.next; // moved pointer but lost link to previous node
} else {
list2 = list2.next;
}
}
return mergedHead;

Correct approach:

ListNode dummy = new ListNode(0);
ListNode current = dummy;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
current.next = list1;
list1 = list1.next;
} else {
current.next = list2;
list2 = list2.next;
}
current = current.next;
}
current.next = (list1 != null) ? list1 : list2;
return dummy.next;

Root cause:

Not updating the 'next' pointers of the merged list and moving input list pointers without linking nodes causes loss of nodes and broken lists.

#2 Forgetting to attach remaining nodes after one list ends.

Wrong approach:

while (list1 != null && list2 != null) {
// merging logic
}
return mergedHead; // missing attaching leftover nodes

Correct approach:

while (list1 != null && list2 != null) {
// merging logic
}
current.next = (list1 != null) ? list1 : list2;
return dummy.next;

Root cause:

Assuming both lists end at the same time and not handling leftover nodes leads to incomplete merged lists.

#3 Using recursion without base cases or on very large lists causing stack overflow.

Wrong approach:

ListNode merge(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val < l2.val) {
l1.next = merge(l1.next, l2);
return l1;
} else {
l2.next = merge(l1, l2.next);
return l2;
}
}
// called on very large lists without iteration fallback

Correct approach:

Use iterative merging for large lists or ensure recursion depth is safe. Iterative version:
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;

Root cause:

Not considering recursion limits in Java can cause runtime errors on large inputs.

Key Takeaways

Merging two sorted linked lists means picking the smaller front node repeatedly to build a new sorted list.

Using a dummy node simplifies the merging code by avoiding special cases for the first node.

You can merge lists by rearranging existing nodes without creating new ones, saving memory.

Both iterative and recursive methods work, but iteration is safer for large lists in Java.

Always attach remaining nodes after one list ends to complete the merged list correctly.

Practice

1. What is the main goal when merging two sorted linked lists?

easy

A. To create a new sorted linked list containing all elements from both lists

B. To reverse both linked lists

C. To find the maximum element in both lists

D. To delete duplicate elements from both lists

Solution

1. Step 1: Understand the input lists

   Two linked lists are sorted individually, meaning their elements are in ascending order.

2. Step 2: Merge while maintaining order

   The goal is to combine these two lists into one sorted list that contains all elements from both.

3. Final Answer:

   To create a new sorted linked list containing all elements from both lists -> Option A

4. Quick Check:

   Merging sorted lists means combining all elements in order [OK]

Hint: Merging means combining sorted lists into one sorted list [OK]

Common Mistakes:

• Thinking merge means reversing lists
• Assuming merge removes duplicates
• Confusing merge with finding max element

2. Which of the following Java method signatures correctly represents a function to merge two sorted linked lists of integers?

easy

A. public int merge(ListNode l1, ListNode l2)

B. public void merge(int l1, int l2)

C. public ListNode merge(ListNode l1, ListNode l2)

D. public ListNode merge(int[] l1, int[] l2)

Solution

1. Step 1: Identify correct parameter types

   The function should accept two linked lists, so parameters must be ListNode types, not primitives or arrays.

2. Step 2: Identify correct return type

   The function returns a merged linked list, so return type should be ListNode, not void or int.

3. Final Answer:

   public ListNode merge(ListNode l1, ListNode l2) -> Option C

4. Quick Check:

   Method with ListNode params and return type is correct [OK]

Hint: Method merges two ListNode inputs and returns ListNode [OK]

Common Mistakes:

• Using primitive types instead of ListNode
• Returning void instead of ListNode
• Using arrays instead of linked lists

3. What is the output linked list after merging these two sorted lists?

List 1: 1 -> 3 -> 5 -> null
List 2: 2 -> 4 -> 6 -> null

medium

A. 2 -> 4 -> 6 -> 1 -> 3 -> 5 -> null

B. 1 -> 3 -> 5 -> 2 -> 4 -> 6 -> null

C. 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null

D. 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Solution

1. Step 1: Compare first nodes of both lists

   1 (List 1) is less than 2 (List 2), so 1 is first in merged list.

2. Step 2: Continue comparing next nodes

   Next compare 3 and 2, 2 is smaller, add 2, then 3 vs 4, add 3, then 5 vs 4, add 4, then 5 vs 6, add 5, finally add 6.

3. Final Answer:

   1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null -> Option D

4. Quick Check:

   Merge keeps ascending order combining both lists [OK]

Hint: Pick smaller head node repeatedly to merge sorted lists [OK]

Common Mistakes:

• Appending one list after the other without sorting
• Reversing order of merged list
• Skipping nodes during merge

4. Given the following code snippet to merge two sorted linked lists, what is the error?

public ListNode merge(ListNode l1, ListNode l2) {
    if (l1 == null) return l2;
    if (l2 == null) return l1;
    if (l1.val < l2.val) {
        l1.next = merge(l1.next, l2);
        return l1;
    } else {
        l2.next = merge(l1, l2.next);
        return l2;
    }
}

medium

A. Missing base case for both lists being null

B. No error; code correctly merges two sorted linked lists

C. Incorrect comparison operator; should be <= instead of <

D. Function does not handle empty lists properly

Solution

1. Step 1: Check base cases

   Code returns the other list if one is null, correctly handling empty lists.

2. Step 2: Check recursive merge logic

   Compares values, recursively merges next nodes, and returns the smaller node, which is correct.

3. Final Answer:

   No error; code correctly merges two sorted linked lists -> Option B

4. Quick Check:

   Recursive merge with base cases is correct [OK]

Hint: Check base cases and recursive calls carefully [OK]

Common Mistakes:

• Forgetting to return merged list
• Incorrect base case handling
• Wrong comparison operator causing order issues

5. You have two sorted linked lists:

List 1: 1 -> 4 -> 5 -> null
List 2: 1 -> 3 -> 4 -> null

After merging, what is the correct merged list?
Also, explain why the merged list contains duplicate values.

hard

A. 1 -> 1 -> 3 -> 4 -> 4 -> 5 -> null

B. 1 -> 3 -> 4 -> 5 -> null

C. 1 -> 4 -> 5 -> 3 -> null

D. 1 -> 1 -> 4 -> 5 -> null

Solution

1. Step 1: Merge nodes in ascending order

   Compare heads: both 1, add both 1s. Then 4 vs 3, add 3. Then 4 vs 4, add both 4s. Finally add 5.

2. Step 2: Understand duplicates in merged list

   Duplicates appear because both lists contain the same values independently; merge keeps all elements without removing duplicates.

3. Final Answer:

   1 -> 1 -> 3 -> 4 -> 4 -> 5 -> null -> Option A

4. Quick Check:

   Merge keeps all elements including duplicates [OK]

Hint: Merge keeps duplicates if present in input lists [OK]

Common Mistakes:

• Removing duplicates during merge
• Appending lists without sorting
• Skipping nodes with same values