Sort a Linked List Using Merge Sort in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to find the middle node of the linked list.

DSA Go

func getMiddle(head *Node) *Node {
    if head == nil {
        return nil
    }
    slow := head
    fast := head
    for fast != nil && fast.Next != nil {
        slow = slow.[1]
        fast = fast.Next.Next
    }
    return slow
}

Drag options to blanks, or click blank then click option'

AHead

BPrev

CNext

DTail

Attempts:

3 left

💡 Hint

Common Mistakes

Using fast pointer instead of slow for moving one step.

Using Prev or Tail which do not exist or are incorrect here.

The slow pointer moves one step at a time using slow.Next to find the middle node.

2fill in blank

medium

Complete the code to merge two sorted linked lists.

DSA Go

func sortedMerge(a, b *Node) *Node {
    if a == nil {
        return b
    }
    if b == nil {
        return a
    }
    var result *Node
    if a.Data <= b.Data {
        result = a
        result.Next = sortedMerge(a.Next, [1])
    } else {
        result = b
        result.Next = sortedMerge([1], b.Next)
    }
    return result
}

Drag options to blanks, or click blank then click option'

Ab

Ba

Cnil

Dresult

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping a and b incorrectly in recursive calls.

Using nil instead of the other list.

When a.Data <= b.Data, we merge the rest of a.Next with b, so the blank is 'b'.

3fill in blank

hard

Fix the error in the mergeSort function to split the list correctly.

DSA Go

func mergeSort(head *Node) *Node {
    if head == nil || head.Next == nil {
        return head
    }
    middle := getMiddle(head)
    nextToMiddle := middle.[1]
    middle.Next = nil
    left := mergeSort(head)
    right := mergeSort(nextToMiddle)
    sortedList := sortedMerge(left, right)
    return sortedList
}

Drag options to blanks, or click blank then click option'

ANext

BPrev

CHead

DTail

Attempts:

3 left

💡 Hint

Common Mistakes

Using Prev or Head which are incorrect here.

Not splitting the list properly causing infinite recursion.

To split the list, we get the node after middle using middle.Next.

4fill in blank

hard

Fill both blanks to complete the mergeSort function that sorts the linked list.

DSA Go

func mergeSort(head *Node) *Node {
    if head == nil || head.Next == nil {
        return head
    }
    middle := [1](head)
    nextToMiddle := middle.[2]
    middle.Next = nil
    left := mergeSort(head)
    right := mergeSort(nextToMiddle)
    sortedList := sortedMerge(left, right)
    return sortedList
}

Drag options to blanks, or click blank then click option'

AgetMiddle

BsortedMerge

CNext

DmergeSort

Attempts:

3 left

💡 Hint

Common Mistakes

Using sortedMerge instead of getMiddle.

Using mergeSort instead of Next for the pointer.

We use getMiddle to find the middle and Next to get the node after middle.

5fill in blank

hard

Fill all three blanks to complete the sortedMerge function that merges two sorted linked lists.

DSA Go

func sortedMerge(a, b *Node) *Node {
    if a == nil {
        return [1]
    }
    if b == nil {
        return [2]
    }
    var result *Node
    if a.Data <= b.Data {
        result = a
        result.Next = sortedMerge(a.Next, [3])
    } else {
        result = b
        result.Next = sortedMerge([3], b.Next)
    }
    return result
}

Drag options to blanks, or click blank then click option'

Ab

Ba

Cnil

Dresult

Attempts:

3 left

💡 Hint

Common Mistakes

Returning nil instead of the other list.

Using result instead of the other list in recursive calls.

If a is nil, return b; if b is nil, return a; recursive calls use the other list accordingly.

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