#148

Medium

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Sort List

Sort List requires sorting a singly linked list efficiently using pointer manipulation and merge sort for optimal performance.

linked list two pointers divide and conquer sorting merge sort

Problem Statement

Given the head of a singly linked list, implement a function that returns the list sorted in ascending order. You must manipulate the node pointers without converting the list into another data structure, ensuring efficiency for large lists.

For example, given head = [4,2,1,3], your function should return [1,2,3,4]. Given head = [-1,5,3,4,0], it should return [-1,0,3,4,5]. The solution should handle lists with up to 50,000 nodes and node values in the range [-105, 105].

Examples

Example 1

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

Output: [1,2,3,4]

Example details omitted.

Example 2

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

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

Example details omitted.

Example 3

Input: head = []

Output: []

Example details omitted.

Constraints

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

Solution Approach

Use Fast and Slow Pointers to Split the List

Apply the two-pointer technique to locate the middle of the linked list, splitting it into two halves. This ensures each recursive merge operates on roughly equal-sized sublists, maintaining O(n log n) time complexity.

Recursive Merge Sort on Sublists

Recursively sort each half of the list by calling the sort function on the left and right segments. This step relies on pointer manipulation instead of array indices and avoids extra array allocation, preserving linked-list efficiency.

Merge Two Sorted Sublists Efficiently

Iteratively or recursively merge the two sorted halves by adjusting the next pointers. Carefully track the head and tail of the merged list to prevent cycles and preserve the ascending order, which is critical in linked-list pointer-based sorting.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log n) due to the divide-and-conquer merge sort approach. Space complexity is O(log n) for recursion stack; no additional arrays are used, keeping pointer manipulation efficient.

What Interviewers Usually Probe

The interviewer may hint at avoiding array conversion for true pointer manipulation.
Expect discussion on fast and slow pointers for splitting the linked list.
They often ask how to merge sublists without extra space to verify understanding of linked-list operations.

Common Pitfalls or Variants

Common pitfalls

Accidentally creating cycles when reconnecting nodes during merge.
Not handling empty lists or single-node lists as base cases, causing null pointer errors.
Failing to update head or tail pointers correctly, leading to lost nodes in the final sorted list.

Follow-up variants

Sort a doubly linked list using similar divide-and-conquer strategies but with backward pointers.
Sort a linked list where nodes contain extra data that must remain paired with values.
Implement iterative bottom-up merge sort instead of recursive sorting to reduce stack usage.

FAQ

What is the most efficient way to sort a linked list in LeetCode 148?

Using merge sort directly on the linked list with careful pointer manipulation ensures O(n log n) time and minimal extra space.

Can I convert the linked list to an array and sort it?

While possible, this approach loses the pointer manipulation pattern and increases space complexity, which may be penalized in interviews.

How do fast and slow pointers help in Sort List?

They locate the middle node efficiently to split the list into halves for recursive merge sort, maintaining balanced recursion.

What are common mistakes when merging sorted linked lists?

Forgetting to update next pointers, losing track of head and tail, or creating cycles are frequent pitfalls that break the sorted list.

Does the solution work for very large lists?

Yes, the O(n log n) merge sort with pointer manipulation handles up to 50,000 nodes efficiently without extra arrays.

terminal

Solution

Solution 1: Merge Sort

We can use the merge sort approach to solve this problem.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:
            return head
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        l1, l2 = head, slow.next
        slow.next = None
        l1, l2 = self.sortList(l1), self.sortList(l2)
        dummy = ListNode()
        tail = dummy
        while l1 and l2:
            if l1.val <= l2.val:
                tail.next = l1
                l1 = l1.next
            else:
                tail.next = l2
                l2 = l2.next
            tail = tail.next
        tail.next = l1 or l2
        return dummy.next

Continue Practicing

#143 reorder list #142 linked list cycle ii #141 linked list cycle