Sort List (Merge Sort on LL)

📋

Problem

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.

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

Edge cases: Empty list → returns empty listSingle node list → returns the same single nodeAll nodes have the same value → returns the same list unchanged

</>

IDE

def sortList(head: Optional[ListNode]) -> Optional[ListNode]:public ListNode sortList(ListNode head)ListNode* sortList(ListNode* head)function sortList(head)

def sortList(head):
    # Write your solution here
    pass

class Solution {
    public ListNode sortList(ListNode head) {
        // Write your solution here
        return null;
    }
}

#include <vector>
using namespace std;

ListNode* sortList(ListNode* head) {
    // Write your solution here
    return nullptr;
}

function sortList(head) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [4, 2, 3, 1]Incorrect splitting of the list; fast/slow pointer technique not used or implemented wrongly.✅ Use two pointers: fast moves two steps, slow moves one step; split list at slow pointer.

Wrong: [1, 2, 3, 4, 5]Output correct but function uses extra space by converting list to array, violating O(1) space constraint.✅ Implement merge sort directly on linked list nodes without array conversion.

Wrong: [2, 2, 2]Nodes lost during merge when values are equal due to incorrect merge condition.✅ Use <= comparison in merge to keep all nodes and maintain stability.

Wrong: [5, 4, 3, 2, 1]Merge step concatenates lists without sorting or merges incorrectly.✅ Merge two sorted lists by comparing node values and linking nodes in ascending order.

Wrong: Function crashes or infinite recursionBase case missing or incorrect for empty or single node list.✅ Add base case: if head is None or head.next is None, return head immediately.

✓

Test Cases

Focus on handling base cases like empty and single node lists correctly.

Test your merge and split functions on tricky inputs with duplicates and reverse order.

Optimize your solution to run efficiently on large inputs using O(n log n) merge sort.

t1_01basic

Input{"head":[4,2,1,3]}

Expected[1,2,3,4]

⏱ Performance - must finish in 2000ms

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

💡 Think about how merge sort splits the list into halves recursively.

💡 Use the fast and slow pointer technique to find the middle of the list for splitting.

💡 Merge two sorted sublists by comparing node values and linking nodes in order.

Why it failed: Basic case failed - likely incorrect splitting or merging logic. Ensure you use fast/slow pointers to split and merge nodes correctly.

✓ Core merge sort logic on linked list is implemented correctly.

t1_02basic

Input{"head":[5,3,8,1,2]}

Expected[1,2,3,5,8]

⏱ Performance - must finish in 2000ms

Sorting a list with 5 nodes results in ascending order [1, 2, 3, 5, 8].

💡 Remember to handle odd-length lists when splitting.

💡 Check that your merge function correctly handles all nodes from both halves.

💡 Ensure the base case returns the node itself when the list has one or zero nodes.

Why it failed: Incorrect output due to improper base case or merge step. Fix base case to return single node and merge to handle all nodes.

✓ Sorting works correctly for odd-length lists.

t2_01edge

Input{"head":[]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty list returns empty list.

💡 Check if the input list is empty or None at the start.

💡 Return None immediately if the list is empty to avoid errors.

💡 Base case: if head is None, return None.

Why it failed: Function crashes or returns non-empty for empty input. Fix by adding base case: if head is None, return None.

✓ Correctly handles empty list input.

t2_02edge

Input{"head":[7]}

Expected[7]

⏱ Performance - must finish in 2000ms

Single node list returns the same single node.

💡 Check base case for single node: return head immediately.

💡 Avoid unnecessary splitting or merging when list length is 1.

💡 Base case: if head.next is None, return head.

Why it failed: Incorrect output or infinite recursion on single node input. Fix base case to return head if head.next is None.

✓ Correctly handles single node list.

t2_03edge

Input{"head":[2,2,2,2]}

Expected[2,2,2,2]

⏱ Performance - must finish in 2000ms

All nodes have the same value; output list remains unchanged.

💡 Ensure merge function handles equal values correctly without losing nodes.

💡 Check that stable ordering is preserved when values are equal.

💡 Merge by comparing <= or < consistently to keep all nodes.

Why it failed: Nodes lost or order changed when values are equal. Fix merge to handle equal values by using <= comparison.

✓ Correctly handles lists with all identical values.

t3_01corner

Input{"head":[5,4,3,2,1]}

Expected[1,2,3,4,5]

⏱ Performance - must finish in 2000ms

Reverse sorted list tests correct splitting and merging order.

💡 Check that splitting divides the list correctly even if sorted descending.

💡 Merge step must reorder nodes properly, not just concatenate.

💡 Use fast/slow pointers to find middle and merge sorted halves correctly.

Why it failed: Output remains reverse sorted or partially sorted. Fix merge to reorder nodes properly, not just append.

✓ Correctly sorts reverse ordered list.

t3_02corner

Input{"head":[1,1,1,2,2,2]}

Expected[1,1,1,2,2,2]

⏱ Performance - must finish in 2000ms

Tests stable sorting and correct handling of duplicates.

💡 Ensure merge is stable: equal values keep original relative order.

💡 Check merge condition uses <= to maintain stability.

💡 Avoid swapping nodes unnecessarily when values are equal.

Why it failed: Sorting is unstable or duplicates lost. Fix merge to use <= comparison to maintain stability.

✓ Stable sorting with duplicates is correct.

t3_03corner

Input{"head":[3,1,2,3,1]}

Expected[1,1,2,3,3]

⏱ Performance - must finish in 2000ms

Tests correct splitting and merging with duplicates and unsorted input.

💡 Verify splitting finds exact middle even with duplicates.

💡 Merge must handle duplicates and reorder correctly.

💡 Check base case and recursive calls handle all nodes.

Why it failed: Incorrect order or missing nodes due to wrong split or merge. Fix splitting to use fast/slow pointers and merge to handle duplicates.

✓ Correctly sorts list with duplicates and unsorted order.

t4_01performance

Input{"head":[100000,99999,99998,99997,99996,99995,99994,99993,99992,99991,99990,99989,99988,99987,99986,99985,99984,99983,99982,99981,99980,99979,99978,99977,99976,99975,99974,99973,99972,99971,99970,99969,99968,99967,99966,99965,99964,99963,99962,99961,99960,99959,99958,99957,99956,99955,99954,99953,99952,99951,99950,99949,99948,99947,99946,99945,99944,99943,99942,99941,99940,99939,99938,99937,99936,99935,99934,99933,99932,99931,99930,99929,99928,99927,99926,99925,99924,99923,99922,99921,99920,99919,99918,99917,99916,99915,99914,99913,99912,99911,99910,99909,99908,99907,99906,99905,99904,99903,99902,99901]}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=100 tests O(n log n) time complexity; must complete within 2 seconds.

💡 Use merge sort with O(n log n) complexity to handle large input efficiently.

💡 Avoid converting linked list to array to maintain O(1) space complexity.

💡 Use fast/slow pointers for splitting and iterative or recursive merge.

Why it failed: TLE due to O(n^2) or worse complexity. Fix by implementing O(n log n) merge sort with fast/slow pointer splitting.

✓ Algorithm runs within time limit confirming O(n log n) complexity.

Practice

1. Given the following Python code implementing the optimal recursive addition of two linked lists representing numbers in forward order, what is the value of the carry returned by addListsHelper when adding lists representing 724 and 564?

easy

A. 1

B. 2

C. 0

D. 3

Solution

1. Step 1: Trace addition from least significant digit

   Adding 4 + 4 = 8, carry 0; next 2 + 6 = 8, carry 0; finally 7 + 5 = 12, carry 1.

2. Step 2: Propagate carry backward

   Carry 1 is returned from the most significant digit addition, indicating an overflow digit.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   724 + 564 = 1288, carry 1 at MSB addition [OK]

Hint: Carry is from MSB addition overflow [OK]

Common Mistakes:

• Ignoring carry from most significant digit
• Off-by-one error in recursion base case
• Misaligning lists before addition

2. Given two singly linked lists that may or may not intersect, which approach guarantees finding the intersection node in O(m + n) time and O(1) space without modifying the lists?

easy

A. Store all nodes of the first list in a hash set, then check each node of the second list against the set.

B. Use nested loops to compare every node in the first list with every node in the second list.

C. Use two pointers starting at each list head, switching heads when reaching the end, to equalize path lengths and find the intersection.

D. Sort both lists by node values and then scan simultaneously to find matching values.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding the intersection node without extra space and in linear time.

2. Step 2: Evaluate approaches

   Nested loops (B) are O(m*n), hash set (C) uses extra space, sorting (D) is invalid as node values may not be unique and sorting modifies lists. The two-pointer approach (A) equalizes path lengths by switching heads, ensuring both pointers traverse equal total lengths and meet at the intersection or end.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two-pointer approach is O(m+n) time and O(1) space [OK]

Hint: Two pointers switching heads equalize lengths [OK]

Common Mistakes:

• Confusing node values with node references
• Using extra space unnecessarily
• Assuming sorting helps with intersection

3. What is the time and space complexity of the optimal in-place iterative merge algorithm for merging two sorted linked lists of lengths n and m?

medium

A. Time: O(max(n, m)), Space: O(1)

B. Time: O(n·m), Space: O(1)

C. Time: O(n + m), Space: O(n + m)

D. Time: O(n + m), Space: O(1)

Solution

1. Step 1: Analyze time complexity

   The algorithm traverses each node exactly once, either from l1 or l2, so total steps are proportional to n + m.

2. Step 2: Analyze space complexity

   It rearranges pointers in-place without allocating new nodes or recursion stack, so auxiliary space is O(1).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time and constant space for in-place merge [OK]

Hint: In-place merge visits each node once, no extra space [OK]

Common Mistakes:

• Confusing time as O(n·m) due to nested loops
• Assuming recursion adds O(n + m) stack space
• Thinking space is O(n + m) due to new list creation

4. What is the time complexity of the optimal linked list rotation algorithm that uses two pointers and connects the tail to the head to form a circular list before breaking it at the new tail?

medium

A. O(n), where n is the length of the list

B. O(k * n), where k is the rotation count and n is the list length

C. O(n + k), where n is list length and k is rotation count

D. O(n^2), due to nested pointer traversals

Solution

1. Step 1: Identify main operations

   Traversing the list once to find length and tail is O(n).

2. Step 2: Pointer movements

   Moving fast pointer k steps and slow pointer until fast reaches tail is at most O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   All operations combined are linear in n [OK]

Hint: Length calculation + single pass pointer moves -> O(n) [OK]

Common Mistakes:

• Assuming O(k*n) due to repeated rotations
• Confusing k with n in complexity
• Thinking nested loops cause O(n^2)

5. Suppose the linked list rotation problem is modified so that k can be negative, indicating rotation to the left by |k| places. Which modification to the optimal algorithm correctly handles negative k values?

hard

A. Ignore negative k and return the original list without rotation.

B. Convert negative k to positive by k = abs(k) and rotate right as usual.

C. Adjust k by k = (k % length + length) % length to normalize negative rotations to equivalent right rotations.

D. Reverse the list first, then apply the original rotation algorithm with positive k.

Solution

1. Step 1: Understand negative rotation meaning

   Negative k means rotate left by |k|, which is equivalent to rotating right by length - |k|.

2. Step 2: Normalize k to positive equivalent

   Using k = (k % length + length) % length converts negative k to correct positive rotation count.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Normalization handles negative rotations correctly [OK]

Hint: Normalize k with modulo to handle negatives [OK]

Common Mistakes:

• Taking absolute value loses rotation direction
• Ignoring negative k leads to wrong output
• Reversing list unnecessarily complicates solution