Why Merge Two Sorted Linked Lists in DSA Go?

The Big Idea

What if you could combine two sorted lists perfectly without lifting a finger?

The Scenario

Imagine you have two lists of names sorted alphabetically on paper. You want to combine them into one sorted list by comparing each name manually and writing them down one by one.

The Problem

Doing this by hand is slow and easy to make mistakes, like skipping a name or putting them out of order. It takes a lot of time and focus, especially if the lists are long.

The Solution

Using the "Merge Two Sorted Linked Lists" method, a computer can quickly and correctly combine two sorted lists into one sorted list by comparing elements step-by-step automatically, without missing or mixing up any items.

Before vs After

✗ Before

for i := 0; i < len(list1); i++ {
  for j := 0; j < len(list2); j++ {
    // compare and insert manually
  }
}

✓ After

func mergeLists(list1, list2 *Node) *Node {
  // merge nodes in sorted order
}

What It Enables

This lets us efficiently combine sorted data streams, making tasks like sorting, searching, and data processing much faster and reliable.

Real Life Example

When merging two sorted contact lists from different phones into one, this method ensures the final list stays alphabetically ordered without duplicates or errors.

Key Takeaways

Manual merging is slow and error-prone.

Automated merging compares and links nodes step-by-step.

It enables fast, reliable combination of sorted data.

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