Sort Linked List

Sort a singly linked list in ascending order. This tests understanding of linked list manipulation and efficient sorting algorithms applicable to non-array data structures.

linked listsortingmerge sortdivide and conquerrecursion

Problem Statement

Given the head of a singly linked list, rearrange the nodes so that they are in ascending order based on their values. You must modify the links between the nodes; you cannot simply swap the values stored in the nodes.

Example 1

Input: 4 -> 2 -> 1 -> 3 -> NULL

Output: 1 -> 2 -> 3 -> 4 -> NULL

The linked list is rearranged so that the nodes are in ascending order: 1, 2, 3, 4.

Example 2

Input: -1 -> 5 -> 3 -> 4 -> 0 -> NULL

Output: -1 -> 0 -> 3 -> 4 -> 5 -> NULL

The linked list is rearranged to place the nodes in ascending order, including negative values and zero.

Constraints

-The number of nodes in the list is in the range [0, 50000].
--10^5 <= Node.val <= 10^5
-You must sort the list in O(n log n) time and O(1) space (under certain merge sort implementations)

Brute Force Approach

The simplest approach is to extract all node values into an array, sort the array using a standard sorting algorithm, and then overwrite the values in the linked list with the sorted values. Imagine you have a train with cars connected in the wrong order; you detach each car, rearrange them on a siding, and then reattach them to the train. This has O(n log n) time complexity due to sorting and O(n) space complexity to store the array.

TimeO(n log n)

SpaceO(n)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem