The challenge
Sort an acyclic singly linked list into nondecreasing order using top-down merge sort.
Reuse the input nodes; the recursive calls use stack space.
Example
[4, 2, 1, 3] → [1, 2, 3, 4].
Use the walkthrough below to inspect the input and each state change.
See Merge sort, step by step
Follow the pointers. Watch each link change.
A1Inspect node links
| Node | Value | Next |
|---|---|---|
| A1 | 4 | A2 |
| A2 | 2 | A3 |
| A3 | 1 | A4 |
| A4 | 3 | null |
Read the input
IDs label node objects. Equal values can belong to different nodes. Solid arrows are next links; dashed arrows are random links.
Start from the input head pointers.View original input
A: 4 (A1) → 2 (A2) → 1 (A3) → 3 (A4); parameters: {}
Parameter indices are zero-based, except n from the end, which is one-based. Node IDs remain fixed when links change.
Put it into code
Lists split naturally with fast/slow pointers and merge without an auxiliary array.
Node stores val and next; the random-pointer lesson adds random. C++ uses C++17 or later.
class Node:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge(a, b):
dummy = Node()
tail = dummy
while a and b:
if a.val <= b.val:
tail.next, a = a, a.next
else:
tail.next, b = b, b.next
tail = tail.next
tail.next = a if a else b
return dummy.next
def sort_list(head):
if head is None or head.next is None:
return head
slow, fast = head, head.next
while fast and fast.next:
slow, fast = slow.next, fast.next.next
right = slow.next
slow.next = None
left = sort_list(head)
right = sort_list(right)
return merge(left, right)
#include <cstddef>
struct Node {
int val;
Node* next;
Node(int value = 0, Node* link = nullptr)
: val(value), next(link) {}
};
Node* merge(Node* a, Node* b) {
Node dummy;
Node* tail = &dummy;
while (a && b) {
if (a->val <= b->val) {
tail->next = a;
a = a->next;
} else {
tail->next = b;
b = b->next;
}
tail = tail->next;
}
tail->next = a ? a : b;
return dummy.next;
}
Node* sort_list(Node* head) {
if (!head || !head->next) return head;
Node* slow = head;
Node* fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
Node* right = slow->next;
slow->next = nullptr;
Node* left = sort_list(head);
right = sort_list(right);
return merge(left, right);
}