Merge Two Sorted Linked Lists in DSA Go - Deep Dive

Overview - Merge Two Sorted Linked Lists

What is it?

Merging two sorted linked lists means combining them into one sorted linked list. Each input list is already sorted from smallest to largest. The goal is to create a new list that keeps this order without changing the original lists. This helps when you want to combine data that is already organized.

Why it matters

Without merging sorted lists efficiently, combining data would be slow and complicated. Imagine trying to merge two sorted phone books by hand without a method. This concept saves time and effort in many programs, like sorting data streams or combining search results. It makes programs faster and easier to understand.

Where it fits

Before this, you should know what a linked list is and how to traverse it. After learning this, you can study more complex list operations like sorting linked lists or merging multiple lists. This is a building block for understanding efficient data handling.

Mental Model

Core Idea

Merging two sorted linked lists means picking the smallest current item from either list step-by-step to build one sorted list.

Think of it like...

Imagine two friends lining up in order of height to enter a room. You let the shorter person enter first, then compare the next in line from both friends, always choosing the shorter next person to keep the line sorted.

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 Basics

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

A linked list is a chain of nodes. Each node holds a value and a link to the next node. The last node points to null, meaning the end of the list. You can move through the list by following these links one by one.

Result

You can represent a list like 1 -> 2 -> 3 -> null and understand how to visit each node.

Knowing how linked lists connect nodes is essential before merging because merging means rearranging these connections.

2

Foundation

What Does Sorted Mean in Lists?

Concept: Understand that sorted means values are in order from smallest to largest.

A sorted list has values arranged so each next value is equal or bigger than the previous. For example, 1 -> 3 -> 5 -> null is sorted, but 3 -> 1 -> 5 -> null is not. This order helps us merge efficiently.

Result

You can quickly find the smallest value by looking at the first node in a sorted list.

Recognizing sorted order lets us pick the smallest next item without searching the whole list.

3

Intermediate

Step-by-Step Merge Process

🤔Before reading on: do you think we should pick the bigger or smaller node first when merging? Commit to your answer.

Concept: Introduce the idea of comparing the current nodes of both lists and picking the smaller one to add to the merged list.

Start with two pointers, one for each list's head. Compare their values. Pick the smaller value node and link it to the merged list. Move that pointer forward. Repeat until one list ends. Then link the rest of the other list.

Result

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

Understanding this comparison and pointer movement is the core of merging sorted lists efficiently.

4

Intermediate

Using a Dummy Node to Simplify Merging

🤔Before reading on: do you think starting the merged list with a dummy node helps or complicates the code? Commit to your answer.

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

Create a dummy node before the merged list starts. Use a pointer to build the list from this dummy. This way, you don't need to check if the merged list is empty each time you add a node. After merging, return dummy.next as the real head.

Result

Code becomes simpler and cleaner, avoiding extra checks for the first node.

Knowing this trick reduces bugs and makes the merge logic easier to follow.

5

Intermediate

Implementing Merge in Go with Pointers

🤔Before reading on: do you think Go uses pointers or copies for linked list nodes? Commit to your answer.

Concept: Show how to write the merge function in Go using pointers to nodes.

In Go, define the ListNode struct: ```go type ListNode struct { Val int Next *ListNode } ``` The complete merge function: ```go func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode { if l1 == nil { return l2 } if l2 == nil { return l1 } dummy := &ListNode{} current := dummy for l1 != nil && l2 != nil { if l1.Val < l2.Val { current.Next = l1 l1 = l1.Next } else { current.Next = l2 l2 = l2.Next } current = current.Next } if l1 != nil { current.Next = l1 } else { current.Next = l2 } return dummy.Next } ``` This reuses existing nodes by changing Next pointers, not copying values. Go's pointers (*ListNode) allow efficient traversal and mutation.

Result

A complete Go function that merges two sorted linked lists into one sorted list.

Understanding pointer manipulation in Go is key to efficient linked list operations.

6

Advanced

Handling Edge Cases in Merging

🤔Before reading on: do you think merging works the same if one list is empty? Commit to your answer.

Concept: Learn how to handle cases when one or both lists are empty or have different lengths.

If one list is empty, return the other list immediately: ```go if l1 == nil { return l2 } if l2 == nil { return l1 } ``` When one list ends before the other, link the remaining nodes directly: ```go if l1 != nil { current.Next = l1 } else { current.Next = l2 } ``` This avoids unnecessary comparisons and keeps the merged list correct.

Result

The merge function works correctly for all input cases, including empty lists.

Knowing how to handle edge cases prevents runtime errors and ensures robustness.

7

Expert

In-Place Merge Without Extra Memory

🤔Before reading on: do you think merging requires creating new nodes or can it reuse existing ones? Commit to your answer.

Concept: Understand that merging can be done by rearranging existing nodes without creating new ones, saving memory.

The code above is already in-place: it adjusts Next pointers of existing nodes (e.g., `current.Next = l1; l1 = l1.Next`). No new nodes are allocated beyond the dummy (which is temporary). This O(1) extra space (ignoring output) is optimal. Time: O(n + m), where n, m are list lengths. Each node visited once.

Result

The merged list reuses all original nodes, preserving memory and improving performance.

Knowing in-place merging is crucial for writing high-performance code in memory-sensitive environments.

Under the Hood

The merge works by maintaining two pointers, each pointing to the current node of the two input lists. At each step, the algorithm compares the values at these pointers and links the smaller node to the merged list. It then advances the pointer of the chosen node. This continues until one list is exhausted, after which the remaining nodes of the other list are linked directly. Internally, this manipulates the Next pointers of nodes without copying data, making it efficient.

Why designed this way?

This method was designed to leverage the sorted property of input lists, avoiding the need to sort again after merging. It reduces time complexity from potentially O(n log n) to O(n), where n is the total number of nodes. Alternatives like concatenating and sorting would be slower. Using pointers to rearrange nodes avoids extra memory use, which is important in systems programming and embedded devices.

┌─────────────┐       ┌─────────────┐
│ List1 Head  │       │ List2 Head  │
│ (pointer1)  │       │ (pointer2)  │
└─────┬───────┘       └─────┬───────┘
      │                     │
      ▼                     ▼
  [Node1] -> [Node3] -> ...  [Node2] -> [Node4] -> ...
      │                     │
      └───── Compare values ─┘
             │
             ▼
       Pick smaller node
             │
             ▼
      Link to merged list
             │
             ▼
      Move pointer forward
             │
             ▼
      Repeat until end
             │
             ▼
      Attach remaining nodes
             │
             ▼
      Merged sorted list head

Myth Busters - 4 Common Misconceptions

Quick: Do you think merging two sorted lists always creates new nodes? Commit yes or no.

Common Belief: Merging two sorted linked lists means creating a brand new list with new nodes.

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

Why it matters: Creating new nodes wastes memory and time. Understanding in-place merging leads to more efficient programs.

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

Common Belief: Even if input lists are sorted, the merged list might not be sorted automatically.

Reality: If both input lists are sorted, the merge process guarantees the merged list is also sorted.

Why it matters: Assuming the merged list is unsorted might lead to unnecessary sorting steps, wasting resources.

Quick: Do you think the order of input lists affects the merged result? Commit yes or no.

Common Belief: Swapping the two input lists changes the merged list order.

Reality: The merged list is the same regardless of which list is first because the merge compares nodes step-by-step.

Why it matters: Knowing this prevents confusion and helps write simpler, order-agnostic code.

Quick: Do you think you must check every node in both lists multiple times? Commit yes or no.

Common Belief: Merging requires scanning nodes multiple times to find the correct order.

Reality: Each node is visited exactly once during merging, making it efficient.

Why it matters: Believing otherwise may cause inefficient code or misunderstanding of algorithm complexity.

Expert Zone

1

The dummy node technique not only simplifies code but also avoids special cases that cause bugs in pointer manipulation.

2

In-place merging preserves node identity, which is important when nodes carry additional metadata or references beyond their value.

3

The merge algorithm's linear time complexity relies entirely on the input lists being sorted; if not, the result is incorrect.

When NOT to use

Avoid this merge method if input lists are not sorted; instead, use sorting algorithms like merge sort or quicksort. For arrays or random access data, merging strategies differ. Also, if you need to keep original lists unchanged, consider copying nodes instead of in-place merging.

Production Patterns

In real systems, merging sorted linked lists is used in external sorting, merging log files, or combining streams of sorted data. It is common in database query execution plans and real-time data processing pipelines where memory efficiency and speed are critical.

Connections

Merge Sort Algorithm

Builds-on

Understanding how to merge two sorted lists is the key step in merge sort, a powerful sorting algorithm that divides data and merges sorted parts efficiently.

Pointer Manipulation in C and Go

Same pattern

Mastering pointer changes in linked list merging helps understand low-level memory management and efficient data structure manipulation in systems programming.

Real-Time Queue Management

Analogous process

Merging sorted lists is like managing multiple queues in real-time systems, where tasks are prioritized and merged based on urgency or arrival time.

Common Pitfalls

#1 Forgetting to move the pointer after linking a node.

Wrong approach:

if l1.Val < l2.Val {
current.Next = l1
// forgot l1 = l1.Next
} else {
current.Next = l2
// forgot l2 = l2.Next
}
current = current.Next

Correct approach:

if l1.Val < l2.Val {
current.Next = l1
l1 = l1.Next
} else {
current.Next = l2
l2 = l2.Next
}
current = current.Next

Root cause:

Not advancing the pointer causes an infinite loop or repeated nodes in the merged list.

#2 Not handling the case when one list is empty at the start.

Wrong approach:

func mergeTwoLists(l1, l2 *ListNode) *ListNode {
// no check for nil lists
dummy := &ListNode{}
current := dummy
// merge loop
return dummy.Next
}

Correct approach:

func mergeTwoLists(l1, l2 *ListNode) *ListNode {
if l1 == nil {
return l2
}
if l2 == nil {
return l1
}
dummy := &ListNode{}
current := dummy
// merge loop
return dummy.Next
}

Root cause:

Ignoring empty inputs leads to nil pointer dereference or incorrect results.

#3 Creating new nodes instead of reusing existing ones.

Wrong approach:

for l1 != nil && l2 != nil {
var newNode *ListNode
if l1.Val < l2.Val {
newNode = &ListNode{Val: l1.Val}
l1 = l1.Next
} else {
newNode = &ListNode{Val: l2.Val}
l2 = l2.Next
}
current.Next = newNode
current = current.Next
}

Correct approach:

for l1 != nil && l2 != nil {
if l1.Val < l2.Val {
current.Next = l1
l1 = l1.Next
} else {
current.Next = l2
l2 = l2.Next
}
current = current.Next
}

Root cause:

Misunderstanding that nodes can be reused leads to unnecessary memory use and slower code.

Key Takeaways

Merging two sorted linked lists means picking the smallest current node from either list step-by-step to build one sorted list.

Using a dummy node simplifies the code by avoiding special cases when starting the merged list.

The merge process can be done in-place by rearranging existing nodes, which saves memory and improves performance.

Handling edge cases like empty lists or different lengths is essential for robust merging.

Understanding this merge technique is foundational for advanced sorting algorithms and efficient data processing.

Practice

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

easy

A. Remove duplicates from both lists without merging

B. Sort each list separately without combining them

C. Create a new sorted linked list containing all elements from both lists

D. Reverse both lists and then merge

Solution

1. Step 1: Understand the merge operation

   Merging means combining two lists into one while keeping the order sorted.

2. Step 2: Identify the goal of merging sorted lists

   The goal is to create a new sorted list that contains all elements from both input lists.

3. Final Answer:

   Create a new sorted linked list containing all elements from both lists -> Option C

4. Quick Check:

   Merge = Combine sorted lists [OK]

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

Common Mistakes:

• Thinking merge means sorting each list separately
• Confusing merge with removing duplicates only
• Assuming merge reverses the lists

2. Which of the following is the correct Go syntax to define a node struct for a singly linked list?

easy

A. Node := struct { val int; next Node }

B. struct Node { int val; Node* next; }

C. class Node { int val; Node next; }

D. type Node struct { val int; next *Node }

Solution

1. Step 1: Recall Go struct syntax

   In Go, structs are defined with 'type Name struct { fields }' and pointers use '*'.

2. Step 2: Check each option

   type Node struct { val int; next *Node } uses correct Go syntax with pointer '*Node' for next node.

3. Final Answer:

   type Node struct { val int; next *Node } -> Option D

4. Quick Check:

   Go struct with pointer = type Node struct { val int; next *Node } [OK]

Hint: Go structs use 'type' and pointers with '*' [OK]

Common Mistakes:

• Using C/C++ or Java syntax in Go
• Missing pointer '*' for next node
• Using := inside struct definition

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

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

Assume the merge function returns the head of the merged list.

medium

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

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

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

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

Solution

1. Step 1: Compare first nodes of both lists

   1 (List1) < 2 (List2), so start merged list with 1.

2. Step 2: Continue comparing next nodes in order

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

3. Final Answer:

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

4. Quick Check:

   Merge sorted lists = sorted combined list [OK]

Hint: Pick smaller node each step to merge sorted lists [OK]

Common Mistakes:

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

4. Given this Go function snippet to merge two sorted linked lists, what is the bug?

func mergeLists(l1, l2 *Node) *Node {
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }
    if l1.val < l2.val {
        l1.next = mergeLists(l1.next, l2)
        return l1
    } else {
        l2.next = mergeLists(l1, l2.next)
        return l2
    }
}

medium

A. No bug, function correctly merges two sorted lists

B. Missing base case for both lists being nil

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

D. Function does not handle cycles in lists

Solution

1. Step 1: Analyze base cases

   Function returns the other list if one is nil, which is correct.

2. Step 2: Check recursive merge logic

   Function compares values and recursively merges the rest correctly.

3. Final Answer:

   No bug, function correctly merges two sorted lists -> Option A

4. Quick Check:

   Recursive merge with base cases = correct [OK]

Hint: Check base cases and recursion for correctness [OK]

Common Mistakes:

• Thinking missing base case for both nil (not needed)
• Confusing < with <= (both work here)
• Ignoring cycle detection (not required here)

5. You have two sorted linked lists:
List1: 1 -> 4 -> 7 -> 10 -> null
List2: 2 -> 3 -> 5 -> 8 -> 12 -> null

Write a Go function to merge these lists iteratively and return the merged list head. What will be the final merged list?

hard

A. 1 -> 2 -> 3 -> 4 -> 5 -> 7 -> 8 -> 10 -> 12 -> null

B. 1 -> 4 -> 7 -> 10 -> 2 -> 3 -> 5 -> 8 -> 12 -> null

C. 2 -> 3 -> 5 -> 8 -> 12 -> 1 -> 4 -> 7 -> 10 -> null

D. 12 -> 10 -> 8 -> 7 -> 5 -> 4 -> 3 -> 2 -> 1 -> null

Solution

1. Step 1: Initialize dummy node and pointer

   Create a dummy node to start merged list and a pointer to track current node.

2. Step 2: Iterate and compare nodes from both lists

   Compare current nodes from List1 and List2, attach smaller to merged list, move pointer forward.

3. Step 3: Attach remaining nodes after one list ends

   Once one list is exhausted, attach the rest of the other list.

4. Final Answer:

   1 -> 2 -> 3 -> 4 -> 5 -> 7 -> 8 -> 10 -> 12 -> null -> Option A

5. Quick Check:

   Iterative merge keeps sorted order [OK]

Hint: Use dummy node and iterate picking smaller nodes [OK]

Common Mistakes:

• Appending lists without sorting
• Forgetting to attach remaining nodes
• Not using a dummy node causing complex code