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

Sort a Linked List Using Merge Sort

📖 Scenario: You have a singly linked list representing a sequence of numbers. You want to sort this list in ascending order efficiently. Merge sort is a great choice because it works well with linked lists.Imagine you have a chain of numbered tags, and you want to arrange them from smallest to largest without breaking the chain.

🎯 Goal: Build a Java program that creates a linked list with specific numbers, sets up a helper variable for the merge sort, implements the merge sort algorithm on the linked list, and finally prints the sorted linked list.

📋 What You'll Learn

Create a singly linked list with exact nodes containing values: 4, 2, 1, 3

Create a helper variable for the head of the linked list

Implement the merge sort algorithm to sort the linked list

Print the sorted linked list in the format: 1 -> 2 -> 3 -> 4 -> null

💡 Why This Matters

🌍 Real World

Sorting linked lists is useful in applications like managing ordered data streams, scheduling tasks, or organizing records where data is naturally linked.

💼 Career

Understanding linked list sorting algorithms like merge sort is important for software engineers working on performance-critical applications, embedded systems, or interview coding challenges.

1

Create the Linked List

Create a class called ListNode with an integer val and a next pointer. Then create a linked list with nodes containing values 4, 2, 1, and 3 in that order. Assign the head of this list to a variable called head.

DSA Java

// Define ListNode class and create linked list with values 4, 2, 1, 3
// Assign the head node to variable head
// Your code here

Hint

Start by defining the ListNode class with val and next. Then link the nodes in order.

2

Create a Helper Variable for Merge Sort

Inside the main method, create a variable called sortedHead and initialize it to null. This will hold the head of the sorted linked list after merge sort.

DSA Java

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class Main {
    public static void main(String[] args) {
        ListNode head = new ListNode(4);
        head.next = new ListNode(2);
        head.next.next = new ListNode(1);
        head.next.next.next = new ListNode(3);
        
        // Create sortedHead variable
        // Your code here
    }
}

Hint

This variable will store the result of the merge sort later.

3

Implement Merge Sort on the Linked List

Add a static method called mergeSort that takes a ListNode head and returns the sorted ListNode. Implement the merge sort algorithm by splitting the list into halves, recursively sorting each half, and merging the sorted halves. Then, inside main, assign sortedHead to the result of mergeSort(head).

DSA Java

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class Main {
    public static void main(String[] args) {
        ListNode head = new ListNode(4);
        head.next = new ListNode(2);
        head.next.next = new ListNode(1);
        head.next.next.next = new ListNode(3);
        
        ListNode sortedHead = mergeSort(head);
    }

    // Implement mergeSort method here
    // Your code here
}

Hint

Use the slow and fast pointer technique to find the middle. Then recursively sort left and right halves and merge them.

4

Print the Sorted Linked List

Add a static method called printList that takes a ListNode head and prints the list values separated by -> and ending with null. Then call printList(sortedHead) inside main to display the sorted list.

DSA Java

Hint

Traverse the list from head to end, printing each value followed by '->', and finish with 'null'.

Practice

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

easy

A. Merge sort is easier to implement with arrays than linked lists.

B. Quicksort is faster on linked lists because it uses less memory.

C. Merge sort does not require random access and works well with linked lists.

D. Quicksort always sorts linked lists in O(n) time.

Solution

1. Step 1: Understand linked list access

   Linked lists do not support fast random access, so algorithms needing it perform poorly.

2. Step 2: Compare merge sort and quicksort

   Merge sort splits and merges lists using pointers, avoiding random access, making it efficient for linked lists.

3. Final Answer:

   Merge sort does not require random access and works well with linked lists. -> Option C

4. Quick Check:

   Merge sort suits linked lists better than quicksort [OK]

Hint: Merge sort fits linked lists due to pointer-based splitting [OK]

Common Mistakes:

• Thinking quicksort is always faster on linked lists
• Assuming arrays and linked lists behave the same
• Ignoring random access needs

2. Which of the following is the correct base case condition in the merge sort function for a linked list?

easy

A. if (head == null) return head.next;

B. if (head == null || head.next == null) return head;

C. if (head.next == null) return null;

D. if (head == null && head.next == null) return null;

Solution

1. Step 1: Identify base case for recursion

   When the list is empty or has one node, it is already sorted.

2. Step 2: Check condition correctness

   Condition 'head == null || head.next == null' correctly checks for empty or single-node list.

3. Final Answer:

   if (head == null || head.next == null) return head; -> Option B

4. Quick Check:

   Base case returns head if list size ≤ 1 [OK]

Hint: Base case: empty or single node list returns itself [OK]

Common Mistakes:

• Using && instead of || in base case
• Returning null incorrectly for single node
• Not handling empty list properly

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

medium

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

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

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

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

Solution

1. Step 1: Split the list into halves

   Split into (4 -> 2) and (1 -> 3).

2. Step 2: Recursively sort halves and merge

   Sort (4 -> 2) to (2 -> 4), sort (1 -> 3) to (1 -> 3), then merge to (1 -> 2 -> 3 -> 4).

3. Final Answer:

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

4. Quick Check:

   Sorted list ascending order [OK]

Hint: Merge sorted halves to get fully sorted list [OK]

Common Mistakes:

• Not splitting list correctly
• Merging without sorting halves
• Mixing node order during merge

4. Identify the error in this merge function snippet for linked lists:

Node merge(Node a, Node b) {
  if (a == null) return b;
  if (b == null) return a;
  if (a.data < b.data) {
    a.next = merge(a.next, b);
    return b;
  } else {
    b.next = merge(a, b.next);
    return a;
  }
}

medium

A. The function does not merge nodes recursively.

B. The base cases do not handle null nodes.

C. The comparison operator should be <= instead of <.

D. The function returns the wrong node after recursion.

Solution

1. Step 1: Analyze return statements

   When a.data < b.data, function should return 'a' but returns 'b' incorrectly.

2. Step 2: Correct return node after recursion

   Return the node chosen as smaller to maintain sorted order; here it should be 'a' or 'b' accordingly.

3. Final Answer:

   The function returns the wrong node after recursion. -> Option D

4. Quick Check:

   Return chosen smaller node to merge correctly [OK]

Hint: Return the smaller node after recursive merge [OK]

Common Mistakes:

• Returning wrong node after recursive call
• Ignoring base cases
• Incorrect comparison operator

5. You have a linked list with nodes: 5 -> 3 -> 8 -> 2 -> 7 -> null. After applying merge sort, what is the correct sorted linked list? Also, explain why merge sort is preferred over bubble sort for this linked list.

hard

A. 2 -> 3 -> 5 -> 7 -> 8 -> null; Merge sort is faster and uses less memory on linked lists.

B. 8 -> 7 -> 5 -> 3 -> 2 -> null; Bubble sort is faster for small lists.

C. 2 -> 3 -> 5 -> 7 -> 8 -> null; Bubble sort is preferred because it is simpler.

D. 5 -> 3 -> 8 -> 2 -> 7 -> null; Merge sort does not work on linked lists.

Solution

1. Step 1: Sort the list using merge sort

   Sorted order is 2 -> 3 -> 5 -> 7 -> 8 -> null after splitting and merging.

2. Step 2: Explain merge sort advantage

   Merge sort is O(n log n) and uses pointers efficiently; bubble sort is O(n²) and inefficient for linked lists.

3. Final Answer:

   2 -> 3 -> 5 -> 7 -> 8 -> null; Merge sort is faster and uses less memory on linked lists. -> Option A

4. Quick Check:

   Sorted list + merge sort efficiency [OK]

Hint: Merge sort is efficient and stable for linked lists [OK]

Common Mistakes:

• Confusing bubble sort as faster
• Incorrect sorted order
• Thinking merge sort can't handle linked lists