Sort a Linked List Using Merge Sort in DSA Go - Build from Scratch

Sort a Linked List Using Merge Sort

📖 Scenario: You have a singly linked list representing a queue of tasks with different priorities. You want to sort this list by priority using merge sort to efficiently organize the tasks.

🎯 Goal: Build a Go program that creates a linked list, sets up a helper variable, implements merge sort on the linked list, and prints the sorted list.

📋 What You'll Learn

Create a singly linked list with exact nodes and values

Add a helper variable for the list length

Implement merge sort to sort the linked list by node value

Print the sorted linked list in the format: value -> value -> ... -> null

💡 Why This Matters

🌍 Real World

Sorting linked lists is useful in systems where data is stored in linked structures, such as task scheduling, memory management, and network packet ordering.

💼 Career

Understanding linked list sorting algorithms like merge sort is important for software engineers working on performance-critical applications and data structure optimization.

1

Create the Linked List

Create a singly linked list with nodes containing these exact integer values in order: 4, 2, 1, 3. Use the struct type ListNode with fields Val int and Next *ListNode. Create a variable called head pointing to the first node.

DSA Go

// Define ListNode struct and create linked list nodes with values 4, 2, 1, 3
// Your code here

Hint

Start by defining the ListNode struct. Then create nodes one by one linking them using the Next pointer.

2

Add Length Helper Variable

Add a variable called length that stores the number of nodes in the linked list starting from head. Use a for loop to count nodes.

DSA Go

package main

import "fmt"

type ListNode struct {
    Val  int
    Next *ListNode
}

func main() {
    head := &ListNode{Val: 4}
    head.Next = &ListNode{Val: 2}
    head.Next.Next = &ListNode{Val: 1}
    head.Next.Next.Next = &ListNode{Val: 3}

    // Calculate length of linked list
    // Your code here
}

Hint

Use a for loop with a variable current starting at head. Increment length until current is nil.

3

Implement Merge Sort on Linked List

Implement a function called mergeSort that takes a *ListNode and returns a sorted *ListNode. Use the merge sort algorithm by splitting the list into halves, recursively sorting each half, and merging them. Also implement a helper function merge to merge two sorted linked lists. Call mergeSort(head) and assign the result back to head.

DSA Go

package main

import "fmt"

type ListNode struct {
    Val  int
    Next *ListNode
}

func main() {
    head := &ListNode{Val: 4}
    head.Next = &ListNode{Val: 2}
    head.Next.Next = &ListNode{Val: 1}
    head.Next.Next.Next = &ListNode{Val: 3}

    length := 0
    for current := head; current != nil; current = current.Next {
        length++
    }

    // Implement mergeSort and merge functions
    // Call mergeSort on head and assign result to head
    // Your code here
}

Hint

Use the fast and slow pointer technique to find the middle of the list. Recursively sort each half and merge them using the merge function.

4

Print the Sorted Linked List

Print the sorted linked list starting from head in the format: 1 -> 2 -> 3 -> 4 -> null. Use a for loop to traverse the list and print each node's value followed by ->. End with null.

DSA Go

package main

import "fmt"

type ListNode struct {
    Val  int
    Next *ListNode
}

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 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 main() {
    head := &ListNode{Val: 4}
    head.Next = &ListNode{Val: 2}
    head.Next.Next = &ListNode{Val: 1}
    head.Next.Next.Next = &ListNode{Val: 3}

    length := 0
    for current := head; current != nil; current = current.Next {
        length++
    }

    head = mergeSort(head)

    // Print the sorted linked list
    // Your code here
}

Hint

Use a for loop to print each node's value followed by ->. After the loop, print null.

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