What happens if you not breaking the list properly when splitting?

Leads to infinite loops or incorrect merges Fix: Set slow.next = None to split the list cleanly

What happens if you incorrectly handling empty or single node lists?

Null pointer exceptions or wrong output Fix: Add base case checks for head == None or head.next == None

What happens if you merging lists without updating tail pointer correctly?

Resulting list may be truncated or malformed Fix: Advance tail pointer after attaching nodes during merge

Interview Prepin-place-linked-listmediumAmazonGoogleFacebook

Sort List (Merge Sort on LL)

Choose your preparation mode4 modes available

Try It Solution Trace

🎯

mediumLINKED_LISTAmazonGoogleFacebook

Imagine you have a long chain of unsorted train cars and you want to reorder them efficiently without detaching and reattaching each car multiple times.

💡 Sorting a linked list is different from sorting arrays because you can't access elements by index directly. Beginners often struggle with splitting and merging linked lists efficiently without extra space.

📋

Problem Statement

Given the head of a singly linked list, sort the list in ascending order and return the sorted list. You must do this in O(n log n) time and O(1) space complexity (in-place).

The number of nodes in the list is in the range [0, 10^5]-10^5 <= Node.val <= 10^5

💡

Example

Input"head = [4, 2, 1, 3]"

Output[1, 2, 3, 4]

The list is sorted by repeatedly splitting and merging sublists until fully sorted.

Empty list → returns empty list
Single node list → returns the same single node
All nodes have the same value → returns the same list unchanged
Already sorted list → returns the same list without changes

⚠️

Common Mistakes

Not breaking the list properly when splitting

Leads to infinite loops or incorrect merges

✅ Set slow.next = None to split the list cleanly

Incorrectly handling empty or single node lists

Null pointer exceptions or wrong output

✅ Add base case checks for head == None or head.next == None

Merging lists without updating tail pointer correctly

Resulting list may be truncated or malformed

✅ Advance tail pointer after attaching nodes during merge

Using recursion without considering stack overflow for large lists

Runtime error due to deep recursion

✅ Use iterative bottom-up merge sort for large inputs

Sorting by swapping node values instead of rearranging nodes

May violate in-place constraints or cause confusion

✅ Merge by changing next pointers, not node values

🧠

Brute Force (Extract to Array, Sort, Rebuild)

💡 This approach exists to build intuition by converting the linked list to an array, sorting it, then reconstructing the list. It’s easy to implement but not in-place and uses extra space.

Intuition

Convert the linked list to an array, sort the array using built-in sorting, then rebuild the linked list from the sorted array.

Algorithm

Traverse the linked list and store all node values in an array.
Sort the array using a built-in efficient sorting algorithm.
Create a new linked list by iterating over the sorted array and creating nodes.
Return the head of the newly created sorted linked list.

💡 This approach is straightforward but uses extra memory and does not leverage linked list properties.

</>

Code

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def sortList(head):
    if not head:
        return None
    arr = []
    current = head
    while current:
        arr.append(current.val)
        current = current.next
    arr.sort()
    dummy = ListNode(0)
    current = dummy
    for val in arr:
        current.next = ListNode(val)
        current = current.next
    return dummy.next

# Example usage:
# head = ListNode(4, ListNode(2, ListNode(1, ListNode(3))))
# sorted_head = sortList(head)
# while sorted_head:
#     print(sorted_head.val, end=' ')
#     sorted_head = sorted_head.next

Line Notes

arr = []Initialize array to store node values for easy sorting

while current:Traverse entire linked list to extract values

arr.sort()Use built-in sort for simplicity and efficiency

for val in arr:Rebuild linked list from sorted values

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

public class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null) return null;
        List<Integer> arr = new ArrayList<>();
        ListNode current = head;
        while (current != null) {
            arr.add(current.val);
            current = current.next;
        }
        Collections.sort(arr);
        ListNode dummy = new ListNode(0);
        current = dummy;
        for (int val : arr) {
            current.next = new ListNode(val);
            current = current.next;
        }
        return dummy.next;
    }

    // Example main method
    // 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);
    //     Solution sol = new Solution();
    //     ListNode sorted = sol.sortList(head);
    //     while (sorted != null) {
    //         System.out.print(sorted.val + " ");
    //         sorted = sorted.next;
    //     }
    // }
}

Line Notes

List<Integer> arr = new ArrayList<>();Store node values in a dynamic array for sorting

while (current != null)Traverse linked list to collect all values

Collections.sort(arr);Sort values using Java's efficient built-in sort

for (int val : arr)Rebuild linked list from sorted values

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* sortList(ListNode* head) {
    if (!head) return nullptr;
    vector<int> arr;
    ListNode* current = head;
    while (current) {
        arr.push_back(current->val);
        current = current->next;
    }
    sort(arr.begin(), arr.end());
    ListNode dummy(0);
    current = &dummy;
    for (int val : arr) {
        current->next = new ListNode(val);
        current = current->next;
    }
    return dummy.next;
}

// Example usage:
// int main() {
//     ListNode* head = new ListNode(4);
//     head->next = new ListNode(2);
//     head->next->next = new ListNode(1);
//     head->next->next->next = new ListNode(3);
//     ListNode* sorted = sortList(head);
//     while (sorted) {
//         cout << sorted->val << " ";
//         sorted = sorted->next;
//     }
//     return 0;
// }

Line Notes

vector<int> arr;Use vector to store node values for sorting

while (current)Traverse linked list to extract all values

sort(arr.begin(), arr.end());Sort values using STL sort

for (int val : arr)Rebuild linked list from sorted values

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

function sortList(head) {
    if (!head) return null;
    const arr = [];
    let current = head;
    while (current) {
        arr.push(current.val);
        current = current.next;
    }
    arr.sort((a, b) => a - b);
    const dummy = new ListNode(0);
    current = dummy;
    for (const val of arr) {
        current.next = new ListNode(val);
        current = current.next;
    }
    return dummy.next;
}

// Example usage:
// let head = new ListNode(4, new ListNode(2, new ListNode(1, new ListNode(3))));
// let sorted = sortList(head);
// while (sorted) {
//     console.log(sorted.val);
//     sorted = sorted.next;
// }

Line Notes

const arr = [];Initialize array to hold node values for sorting

while (current)Traverse linked list to collect all values

arr.sort((a, b) => a - b);Sort array numerically in ascending order

for (const val of arr)Rebuild linked list from sorted values

⏱

Complexity

TimeO(n log n)

SpaceO(n)

Extracting values takes O(n), sorting takes O(n log n), rebuilding takes O(n). Extra space is O(n) for the array.

💡 For n=20, this means about 20*log2(20) ≈ 86 operations plus storing 20 values in an array.

Interview Verdict: Accepted but not in-place; uses extra memory

This approach is easy to implement but doesn't meet the in-place constraint; good for initial understanding.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	`O(n log n)`	`O(n)`	No	Yes	Mention only - never code
2. Recursive Merge Sort	`O(n log n)`	`O(log n) recursion stack`	Yes (deep recursion)	Yes	Code this in most interviews
3. Bottom-Up Iterative Merge Sort	`O(n log n)`	`O(1) auxiliary`	No	Yes	Code if asked for no recursion or optimal space

Practice

(1/5)

1. You are given a sorted linked list where some elements appear more than once consecutively. The task is to remove all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Which approach guarantees an optimal solution for this problem?

easy

A. Use a brute force nested loop to compare each node with all others and remove duplicates.

B. Use a single-pass iterative approach with a dummy head to skip all duplicates in one traversal.

C. Use a greedy approach that removes duplicates as soon as they are found without revisiting nodes.

D. Use dynamic programming to store counts of each value and then reconstruct the list.

2. Given the following tail-recursive reversal code, what is the output printed when the input linked list is 1 -> 2 -> 3?

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseList(head):
    def helper(prev, curr):
        if not curr:
            return prev
        next_temp = curr.next
        curr.next = prev
        return helper(curr, next_temp)
    return helper(None, head)

head = ListNode(1, ListNode(2, ListNode(3)))
new_head = reverseList(head)
curr = new_head
while curr:
    print(curr.val, end=' ')
    curr = curr.next
print()

easy

A. 3 2 1

B. 1 2 3

C. 3 1 2

D. 2 3 1

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Intuition

Algorithm

Intuition

Algorithm

Intuition

Algorithm

How to Present

Time Allocation

What the Interviewer Tests

Common Follow-ups

When to Use

Signature Phrases

NOT This Pattern When

Similar Problems

Practice

Solution

Step 1: Understand problem constraints

Step 2: Evaluate approaches

Final Answer:

Quick Check:

Solution

Step 1: Trace helper calls

Step 2: Print reversed list

Final Answer:

Quick Check:

Solution

Step 1: Analyze time complexity

Step 2: Analyze space complexity

Final Answer:

Quick Check:

Solution

Step 1: Understand pointer updates

Step 2: Identify bug in pointer advancement

Final Answer:

Quick Check:

Solution

Step 1: Understand circular list implications

Step 2: Modify base case to detect cycle

Step 3: Compare alternatives

Final Answer:

Quick Check:

Ready to prove it?