Sort a Linked List Using Merge Sort in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Merge Sort on a Linked List

What is the printed state of the linked list after applying merge sort on the list 4 -> 2 -> 1 -> 3 -> null?

DSA Go

type ListNode struct {
    Val  int
    Next *ListNode
}

func printList(head *ListNode) string {
    if head == nil {
        return "null"
    }
    result := ""
    for head != nil {
        result += fmt.Sprintf("%d -> ", head.Val)
        head = head.Next
    }
    result += "null"
    return result
}

func mergeSort(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    slow, fast := head, head.Next
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    mid := slow.Next
    slow.Next = nil
    left := mergeSort(head)
    right := mergeSort(mid)
    return merge(left, right)
}

func merge(l1, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    tail := dummy
    for l1 != nil && l2 != nil {
        if l1.Val < l2.Val {
            tail.Next = l1
            l1 = l1.Next
        } else {
            tail.Next = l2
            l2 = l2.Next
        }
        tail = tail.Next
    }
    if l1 != nil {
        tail.Next = l1
    } else {
        tail.Next = l2
    }
    return dummy.Next
}

func main() {
    head := &ListNode{4, &ListNode{2, &ListNode{1, &ListNode{3, nil}}}}
    sorted := mergeSort(head)
    fmt.Println(printList(sorted))
}

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

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

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

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

💡 Hint

Think about how merge sort splits and merges the list in sorted order.

Merge sort splits the list into halves recursively and merges them back in sorted order. The final sorted list is 1 -> 2 -> 3 -> 4 -> null.

🧠 Conceptual

intermediate

Why Use Merge Sort for Linked Lists?

Which reason best explains why merge sort is preferred for sorting linked lists over quicksort or other algorithms?

A Merge sort uses less memory than quicksort for arrays.

B Merge sort does not require random access and works efficiently with linked list pointers.

C Merge sort is faster than any other sorting algorithm in all cases.

D Merge sort sorts the list in place without changing pointers.

💡 Hint

Think about how linked lists store data and how merge sort handles splitting and merging.

Merge sort works well with linked lists because it only needs to change pointers and does not require random access like quicksort or heapsort.

🔧 Debug

advanced

Identify the Bug in Merge Function

What error will occur when running this merge function on two sorted linked lists?

DSA Go

func merge(l1, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    tail := dummy
    for l1 != nil && l2 != nil {
        if l1.Val <= l2.Val {
            tail.Next = l1
            l1 = l1.Next
        } else {
            tail.Next = l2
            l2 = l2.Next
        }
        tail = tail.Next
    }
    tail.Next = l1
    tail.Next = l2
    return dummy.Next
}

A The merged list will be correct with no errors.

B The merged list will contain only elements from l1.

C The merged list will contain only elements from l2.

D The code causes a runtime nil pointer dereference.

💡 Hint

Check how tail.Next is assigned after the loop.

The code assigns tail.Next to l1, then immediately overwrites it with l2, losing the l1 tail. So only l2 elements remain after the loop.

❓ Predict Output

advanced

Output After Sorting a Reverse Sorted List

What is the printed linked list after sorting 5 -> 4 -> 3 -> 2 -> 1 -> null using merge sort?

DSA Go

head := &ListNode{5, &ListNode{4, &ListNode{3, &ListNode{2, &ListNode{1, nil}}}}}
sorted := mergeSort(head)
fmt.Println(printList(sorted))

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

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

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

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

💡 Hint

Merge sort always sorts the list in ascending order.

Merge sort splits and merges the list recursively, resulting in a sorted list from smallest to largest.

🧠 Conceptual

expert

Time Complexity of Merge Sort on Linked List

What is the time complexity of merge sort when sorting a linked list of n nodes?

A O(n log n) because the list is split and merged recursively.

B O(n^2) because each merge scans the entire list.

C O(log n) because splitting halves the list each time.

D O(n) because linked lists allow fast merges.

💡 Hint

Consider how many times the list is split and how merging works.

Merge sort splits the list log n times and merges all n elements each time, resulting in O(n log n) complexity.

Practice

1. What is the main advantage of using merge sort to sort a linked list compared to other sorting algorithms?

easy

A. It sorts the list by comparing only the first and last elements.

B. It sorts the list by swapping adjacent nodes only.

C. It uses a simple loop to sort the list in one pass.

D. It does not require extra space for arrays and works efficiently with linked lists.

Solution

1. Step 1: Understand merge sort with linked lists

   Merge sort splits the list into halves recursively and merges sorted halves. It works well with linked lists because it does not need random access.

2. Step 2: Compare with other sorting methods

   Other sorts like quicksort or bubble sort may require extra space or inefficient node access. Merge sort uses pointers efficiently without extra arrays.

3. Final Answer:

   It does not require extra space for arrays and works efficiently with linked lists. -> Option D

4. Quick Check:

   Merge sort suits linked lists due to pointer use, no extra array needed [OK]

Hint: Merge sort fits linked lists as it uses pointers, no arrays needed [OK]

Common Mistakes:

• Thinking merge sort swaps adjacent nodes only
• Assuming merge sort sorts in one pass
• Believing merge sort compares only first and last elements

2. Which of the following Go function signatures correctly represents the merge function used in merge sort for linked lists?

easy

A. func merge(left []int, right []int) []int

B. func merge(left *Node, right *Node) *Node

C. func merge(left Node, right Node) Node

D. func merge(left *Node, right *Node) int

Solution

1. Step 1: Identify parameter types for linked list nodes

   Linked lists use pointers to nodes, so parameters must be pointers: *Node.

2. Step 2: Identify return type for merged list head

   The merge function returns the head pointer of the merged sorted list, so return type is *Node.

3. Final Answer:

   func merge(left *Node, right *Node) *Node -> Option B

4. Quick Check:

   Merge uses pointers and returns pointer to merged list head [OK]

Hint: Merge function uses pointers to nodes and returns pointer head [OK]

Common Mistakes:

• Using value types instead of pointers for nodes
• Returning int instead of node pointer
• Using slices instead of linked list nodes

3. Given the linked list: 4 -> 2 -> 1 -> 3 -> null, what is the sorted linked list after applying merge sort?

medium

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

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

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

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

Solution

1. Step 1: Split the list recursively

   Split into halves: (4 -> 2) and (1 -> 3). Then split further until single nodes.

2. Step 2: Merge sorted halves

   Merge single nodes in order: 2 -> 4 and 1 -> 3 become 1 -> 2 -> 3 -> 4.

3. Final Answer:

   1 -> 2 -> 3 -> 4 -> null -> Option C

4. Quick Check:

   Sorted order is ascending: 1, 2, 3, 4 [OK]

Hint: Merge sort outputs ascending sorted list [OK]

Common Mistakes:

• Confusing merge order and producing descending list
• Not splitting list fully before merging
• Mixing node values during merge

4. In the following Go code snippet for merge sort on a linked list, what is the error?

func mergeSort(head *Node) *Node {
    if head == nil || head.next == nil {
        return head
    }
    mid := getMiddle(head)
    left := head
    right := mid.next
    mid.next = nil
    left = mergeSort(left)
    right = mergeSort(right)
    return merge(left, right)
}

func getMiddle(head *Node) *Node {
    slow, fast := head, head.next
    for fast != nil && fast.next != nil {
        slow = slow.next
        fast = fast.next.next
    }
    return slow
}

medium

A. No error; code correctly splits and merges the list.

B. getMiddle should initialize fast as head, not head.next.

C. mid.next = nil should be after recursive calls.

D. mergeSort should return void, not *Node.

Solution

1. Step 1: Analyze getMiddle function

   Fast starts at head.next to find middle node correctly for even length lists.

2. Step 2: Check mergeSort logic

   Splits list at mid, sets mid.next to nil to break list, recursively sorts left and right, then merges.

3. Final Answer:

   No error; code correctly splits and merges the list. -> Option A

4. Quick Check:

   Code uses standard merge sort steps correctly [OK]

Hint: Check pointer moves carefully; this code matches standard pattern [OK]

Common Mistakes:

• Initializing fast pointer incorrectly causing wrong middle
• Breaking list after recursion causing infinite loops
• Wrong return type for mergeSort function

5. You have a linked list with duplicate values: 5 -> 3 -> 8 -> 3 -> 5 -> null. After applying merge sort, what will be the correct sorted linked list?

hard

A. 3 -> 3 -> 5 -> 5 -> 8 -> null

B. 5 -> 3 -> 8 -> 3 -> 5 -> null

C. 3 -> 5 -> 8 -> 3 -> 5 -> null

D. 8 -> 5 -> 5 -> 3 -> 3 -> null

Solution

1. Step 1: Understand merge sort handles duplicates

   Merge sort compares node values and merges in ascending order, preserving duplicates in sorted order.

2. Step 2: Sort the list step-by-step

   Splitting and merging results in sorted order: 3, 3, 5, 5, 8.

3. Final Answer:

   3 -> 3 -> 5 -> 5 -> 8 -> null -> Option A

4. Quick Check:

   Duplicates appear in sorted order, merge sort preserves all nodes [OK]

Hint: Merge sort keeps duplicates sorted in ascending order [OK]

Common Mistakes:

• Removing duplicates accidentally during merge
• Sorting incorrectly and mixing node order
• Assuming duplicates are removed automatically