Merge Two Sorted Linked Lists in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of merging two sorted linked lists

What is the printed state of the merged linked list after merging these two sorted lists?

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

DSA Go

package main

import "fmt"

type ListNode struct {
    Val  int
    Next *ListNode
}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    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
}

func printList(head *ListNode) {
    for head != nil {
        fmt.Printf("%d -> ", head.Val)
        head = head.Next
    }
    fmt.Println("null")
}

func main() {
    l1 := &ListNode{1, &ListNode{3, &ListNode{5, nil}}}
    l2 := &ListNode{2, &ListNode{4, &ListNode{6, nil}}}
    merged := mergeTwoLists(l1, l2)
    printList(merged)
}

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

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

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

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

💡 Hint

Remember the merge process compares nodes one by one and links the smaller node first.

The merge function compares the current nodes of both lists and appends the smaller one to the merged list. This results in a sorted merged list combining all nodes.

❓ Predict Output

intermediate

Output when one list is empty

What is the printed state of the merged linked list after merging these two lists?

List 1: null
List 2: 0 -> 7 -> 8 -> null

DSA Go

package main

import "fmt"

type ListNode struct {
    Val  int
    Next *ListNode
}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    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
}

func printList(head *ListNode) {
    for head != nil {
        fmt.Printf("%d -> ", head.Val)
        head = head.Next
    }
    fmt.Println("null")
}

func main() {
    var l1 *ListNode = nil
    l2 := &ListNode{0, &ListNode{7, &ListNode{8, nil}}}
    merged := mergeTwoLists(l1, l2)
    printList(merged)
}

A 0 -> null

B 7 -> 8 -> 0 -> null

C 0 -> 7 -> 8 -> null

D null

💡 Hint

If one list is empty, the merged list is just the other list.

Since l1 is empty, the merged list is just l2 unchanged.

🔧 Debug

advanced

Identify the bug in this merge function

What error or problem will occur when running this merge function code?

DSA Go

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    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
    }
    return dummy.Next
}

A Compilation error due to missing return statement

B Infinite loop because l1 and l2 never change

C Correct output with merged sorted list

D Runtime panic: invalid memory address or nil pointer dereference

💡 Hint

Check the loop condition and what happens when l1 or l2 is nil.

The loop uses || (or) so when one list is nil, accessing l1.Val or l2.Val causes a nil pointer dereference panic.

❓ Predict Output

advanced

Output after merging lists with duplicate values

What is the printed state of the merged linked list after merging these two sorted lists?

List 1: 1 -> 3 -> 5 -> 7 -> null
List 2: 3 -> 5 -> 7 -> 9 -> null

DSA Go

package main

import "fmt"

type ListNode struct {
    Val  int
    Next *ListNode
}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    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
}

func printList(head *ListNode) {
    for head != nil {
        fmt.Printf("%d -> ", head.Val)
        head = head.Next
    }
    fmt.Println("null")
}

func main() {
    l1 := &ListNode{1, &ListNode{3, &ListNode{5, &ListNode{7, nil}}}}
    l2 := &ListNode{3, &ListNode{5, &ListNode{7, &ListNode{9, nil}}}}
    merged := mergeTwoLists(l1, l2)
    printList(merged)
}

A 1 -> 3 -> 5 -> 7 -> 9 -> null

B 1 -> 3 -> 3 -> 5 -> 5 -> 7 -> 7 -> 9 -> null

C 3 -> 3 -> 5 -> 5 -> 7 -> 7 -> 9 -> null

D 1 -> 3 -> 5 -> 7 -> null

💡 Hint

Duplicates from both lists appear in the merged list in sorted order.

The merge includes all nodes from both lists, so duplicates appear in order.

🧠 Conceptual

expert

Time complexity of merging two sorted linked lists

What is the time complexity of merging two sorted linked lists of lengths m and n?

A O(m + n)

B O(m * n)

C O(max(m, n)^2)

D O(log(m + n))

💡 Hint

Consider how many nodes are processed in total during the merge.

Each node from both lists is visited exactly once, so the total time is proportional to the sum of their lengths.

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