# 148. Sort List

Reference: LeetCode
Difficulty: MediumSlow/Fast Pointers

## Problem

Sort a linked list in $O(N\log{N})$ time using constant space complexity.

Example:

## Analysis

### Naive (Extra Space)

Note: Be careful of linked list generation.

Time: $O(N + N\log{N} + N) = O(N\log{N})$
Space: $O(N)$

### Mergesort + Slow/Fast Pointers

#### Recursion

Note:

• It seems bad to use right-leaning splitInHalf, because you can’t split the list (set the previous node of mid to null).
• Since we need to set mid.next to null, we can do right mergeSort first. Clean code.

Time: $O(N\log{N})$
Space: $O(\log{N})$

#### Iteration

Each time we double n.

• split(head, n) that splits input head into [n nodes, the rest].
• We need to handle a case that n is larger than the number of available nodes.
• mergeList(n1, n2) returns [head, tail] of the merged list.

Note: In each loop, p should be initialized with dummy.next rather than head, since head might be changing.

Helper functions:

#### Tips for Slow/Fast Pointers

Note: Use two pointers to find the middle node in the list. But there are two cases: left-leaning and right-leaning.

The difference lies in the while condition.

• Left-leaning: while (fast.next != null && fast.next.next != null) You can see this as a stricter constraint
• Right-leaning: while (fast != null && fast.next != null)

Comment
Junhao Wang
a software engineering cat