Sort a Linked List Using Merge Sort in DSA Javascript - 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 way to sort linked lists because it works well with their structure.

🎯 Goal: Build a JavaScript program that sorts a singly linked list using the merge sort algorithm.You will create the linked list, write helper functions to split and merge lists, and then apply merge sort to get a sorted list.

📋 What You'll Learn

Create a singly linked list with exact nodes: 4 -> 2 -> 1 -> 3 -> null

Create a variable head pointing to the start of the list

Write a function merge that merges two sorted linked lists

Write a function mergeSort that sorts the linked list using merge sort

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

💡 Why This Matters

🌍 Real World

Sorting linked lists is useful in systems where data is stored in linked structures, such as memory management, file systems, and real-time data processing.

💼 Career

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

1

Create the Linked List

Create a class called ListNode with a constructor that takes val and next (default to null). Then create nodes with values 4, 2, 1, 3 and link them to form the list 4 -> 2 -> 1 -> 3 -> null. Finally, create a variable called head that points to the first node (value 4).

DSA Javascript

# Your code here to create ListNode class and linked list nodes

Hint

Remember to link each node's next to the following node to form the list.

2

Write the Merge Function

Write a function called merge that takes two sorted linked lists l1 and l2 and returns a single sorted linked list by merging them. Use variables dummy and tail to build the merged list.

DSA Javascript

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

const node4 = new ListNode(3);
const node3 = new ListNode(1, node4);
const node2 = new ListNode(2, node3);
const head = new ListNode(4, node2);

// Write merge function below

Hint

Use a dummy node to simplify merging and move the tail pointer as you add nodes.

3

Write the Merge Sort Function

Write a function called mergeSort that takes the head of a linked list and returns the sorted linked list. Use the fast and slow pointer technique to find the middle, split the list, recursively sort each half, and then merge them using the merge function.

DSA Javascript

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

const node4 = new ListNode(3);
const node3 = new ListNode(1, node4);
const node2 = new ListNode(2, node3);
const head = new ListNode(4, node2);

function merge(l1, l2) {
    const dummy = new ListNode(0);
    let tail = dummy;
    while (l1 !== null && l2 !== null) {
        if (l1.val < l2.val) {
            tail.next = l1;
            l1 = l1.next;
        } else {
            tail.next = l2;
            l2 = l2.next;
        }
        tail = tail.next;
    }
    tail.next = l1 !== null ? l1 : l2;
    return dummy.next;
}

// Your code here to write mergeSort function

Hint

Use two pointers to find the middle and split the list, then sort each half recursively.

4

Print the Sorted Linked List

Call mergeSort with head and store the result in sortedHead. Then write a loop to print the sorted linked list values separated by -> and ending with null. Use console.log to print the final string.

DSA Javascript

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

const node4 = new ListNode(3);
const node3 = new ListNode(1, node4);
const node2 = new ListNode(2, node3);
const head = new ListNode(4, node2);

function merge(l1, l2) {
    const dummy = new ListNode(0);
    let tail = dummy;
    while (l1 !== null && l2 !== null) {
        if (l1.val < l2.val) {
            tail.next = l1;
            l1 = l1.next;
        } else {
            tail.next = l2;
            l2 = l2.next;
        }
        tail = tail.next;
    }
    tail.next = l1 !== null ? l1 : l2;
    return dummy.next;
}

function mergeSort(head) {
    if (head === null || head.next === null) {
        return head;
    }
    let slow = head;
    let fast = head;
    let prev = null;
    while (fast !== null && fast.next !== null) {
        prev = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    prev.next = null; // split the list
    const left = mergeSort(head);
    const right = mergeSort(slow);
    return merge(left, right);
}

// Your code here to print sorted linked list

Hint

Traverse the sorted list and build a string with arrows, then print it.

Practice

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

easy

A. Merge sort uses less memory than bubble sort for arrays.

B. Merge sort efficiently handles linked lists without random access.

C. Merge sort sorts elements in place without extra space.

D. Merge sort is the fastest sorting algorithm for small arrays.

Solution

1. Step 1: Understand linked list access

   Linked lists do not support random access, so algorithms relying on index access are inefficient.

2. Step 2: Analyze merge sort suitability

   Merge sort works by splitting and merging lists using pointers, which fits linked lists well without needing random access.

3. Final Answer:

   Merge sort efficiently handles linked lists without random access. -> Option B

4. Quick Check:

   Linked list + merge sort = efficient pointer-based sorting [OK]

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

Common Mistakes:

• Thinking merge sort sorts in place for linked lists
• Confusing merge sort speed with bubble sort
• Assuming random access is needed for merge sort

2. Which of the following is the correct way to split a linked list into two halves in JavaScript for merge sort?

easy

A. Use a for loop to iterate half the length and split at midpoint index.

B. Use array slicing to split the linked list into two arrays.

C. Use recursion to split the list by removing the head each time.

D. Use two pointers: slow moves 1 step, fast moves 2 steps until fast reaches end.

Solution

1. Step 1: Identify splitting method for linked list

   Since linked lists lack indexes, we use two pointers: slow and fast to find midpoint.

2. Step 2: Explain pointer movement

   Slow pointer moves one node at a time, fast pointer moves two nodes; when fast reaches end, slow is at midpoint.

3. Final Answer:

   Use two pointers: slow moves 1 step, fast moves 2 steps until fast reaches end. -> Option D

4. Quick Check:

   Two-pointer technique splits linked list correctly [OK]

Hint: Use slow/fast pointers to find midpoint in linked list [OK]

Common Mistakes:

• Trying to use array methods on linked lists
• Using loops with indexes on linked lists
• Splitting by removing head repeatedly

3. What will be the output linked list after applying merge sort on the list: 4 -> 2 -> 1 -> 3 -> null?

medium

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

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

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

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

Solution

1. Step 1: Split the list into halves

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

2. Step 2: Recursively sort and merge halves

   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 ascending list = 1->2->3->4 [OK]

Hint: Merge sort outputs sorted ascending linked list [OK]

Common Mistakes:

• Confusing merge order and producing descending list
• Not fully sorting sublists before merging
• Incorrectly splitting the list

4. Given this merge sort code snippet for linked lists, what is the bug?

function mergeSort(head) {
  if (!head || !head.next) return head;
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  let mid = slow.next;
  slow.next = null;
  let left = mergeSort(head);
  let right = mergeSort(mid);
  return merge(left, right);
}

medium

A. The mid pointer should be slow, not slow.next.

B. Slow pointer should start at head.next, not head.

C. Fast pointer should start at head.next, not head.

D. The base case should check only for head.next, not head.

Solution

1. Step 1: Analyze pointer initialization

   Fast pointer starting at head causes incorrect midpoint for even length lists.

2. Step 2: Correct mid pointer assignment

   The mid pointer should be slow, not slow.next, to correctly split the list into two halves.

3. Final Answer:

   The mid pointer should be slow, not slow.next. -> Option A

4. Quick Check:

   Mid pointer assignment = slow for correct split [OK]

Hint: Mid pointer must be slow for correct split [OK]

Common Mistakes:

• Starting fast pointer at head
• Misplacing mid pointer assignment
• Incorrect base case conditions

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

hard

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

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

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

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

Solution

1. Step 1: Understand merge sort handles duplicates

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

2. Step 2: Sort and merge duplicates

   Sorting 3->1->2->3->2 results in 1->2->2->3->3 as duplicates remain in sorted order.

3. Final Answer:

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

4. Quick Check:

   Duplicates sorted and preserved in ascending order [OK]

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

Common Mistakes:

• Removing duplicates by mistake
• Sorting incorrectly in descending order
• Confusing linked list with array sorting