Sort a Linked Chain
Problem
Given the head of a singly linked list of numbers, return the head of the same nodes relinked into ascending order. Nodes may not be copied into a Python list and sorted there; the answer should relink the existing nodes in O(n log n) time. The list may be empty.
Examples
Input: 4 -> 1 -> 3 -> 1 -> 2
Output: 1 -> 1 -> 2 -> 3 -> 4
Why: duplicates are kept, only the links changeInput: -3 -> 8
Output: -3 -> 8
Why: already in order, so the relinking is a no-opInput: empty
Output: empty
Why: edge case, an empty chain is already sortedHints
0 / 3
Quick sort needs to jump around by index, which a chain cannot do cheaply. Pick the sort that only ever reads its input front to back.
Merge sort fits: split the chain into two halves, sort each half, and merge two sorted chains by always taking the smaller head.
Find the middle with a slow pointer that takes one step while a fast pointer takes two, then cut the link after the slow pointer. Sort both halves recursively and merge them behind a placeholder node, attaching whatever remains of the longer half at the end.
Solution
Merge sort suits a chain because splitting and merging only ever walk forward along the links. The slow and fast pointers find the middle in one pass, and cutting the link there gives two independent chains. Merging behind a placeholder node relinks existing nodes without allocating new ones, and taking from the left chain on ties keeps the sort stable. Time is O(n log n), and space is O(log n) for the recursion.
class N:
def __init__(self, val, nxt=None): self.val, self.next = val, nxt
def build(v): return N(v[0], build(v[1:])) if v else None # list -> chain
def dump(h): return [h.val] + dump(h.next) if h else [] # chain -> list
def sort_chain(head):
if head is None or head.next is None:
return head # zero or one node is already sorted
slow, fast = head, head.next
while fast and fast.next: # slow stops at the end of the left half
slow, fast = slow.next, fast.next.next
right, slow.next = slow.next, None # cut the chain in two
a, b = sort_chain(head), sort_chain(right)
tail = dummy = N(0)
while a and b: # merge: always take the smaller head
if a.val <= b.val:
tail.next, a = a, a.next
else:
tail.next, b = b, b.next
tail = tail.next
tail.next = a or b # one side may still have nodes
return dummy.next
print(dump(sort_chain(build([4, 1, 3, 1, 2])))) # -> [1, 1, 2, 3, 4]
print(dump(sort_chain(build([-3, 8])))) # -> [-3, 8]
print(dump(sort_chain(build([])))) # -> []Stuck on the idea rather than the code? Merge Sort covers it.