Sort a linked list in O(n log n) time and constant space

January 20, 2025 · 1 min · daily-coding-problem | 🖍️

Table of Contents

Problem

Given a linked list, sort it in O(n log n) time and constant space.

Example 1:

1
2


Input: head = [4,2,1,3]
Output: [1,2,3,4]

We have already seen Sort a Linked List, but here we have to sort in O(n log n) time and O(1) space. So, we can use merge sort to meet the constraints. Merge Sort in a Linked list#Method 1 - Recursive