Sort List · Interview Problem

Back to problems

Leetcode

Medium

Linked Lists

Sorting

Divide and Conquer

Google

Sort List

Sort a singly linked list in ascending order with better-than-quadratic performance.

Acceptance 100%

Start Practice

Problem Statement

Problem

Given the head of a singly linked list, sort the list in ascending order and return the head of the sorted list.

You should aim for an efficient solution that performs well on large lists. Since the list is singly linked, a solution that repeatedly inserts or searches linearly at every step is typically too slow.

Notes

Reorder the existing nodes; do not create a separate array-based solution unless you are only using it for reasoning.
The relative order of equal values does not need to be preserved unless your implementation naturally keeps it stable.

Goal

Return the head of the list after sorting all node values in nondecreasing order.

Input Format

A singly linked list head node head.
Each node contains an integer value.

Output Format

Return the head node of the linked list after it has been sorted in ascending order.

Constraints

The list may be empty.
The list may contain duplicate values.
Values may be negative, zero, or positive.
A solution with $O(n \log n)$ time is expected for an interview-quality answer.

Examples

Sample cases returned by the problem API.

Example 1

Input

head = [4,2,1,3]

Output

[1,2,3,4]

Explanation

The nodes are reordered so that the values appear in ascending order.

Example 2

Input

head = [-1,5,3,4,0]

Output

[-1,0,3,4,5]

Explanation

After sorting, the linked list is arranged from smallest to largest value.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress