Practice › Linked List
Sort a Linked List
Medium · Linked List · Asked at Amazon, Microsoft, Meta, Bloomberg
Sort the linked list in non-decreasing order in O(n log n) time and print it.
Input
First line: n. Second line: the n node values from head to tail.
Output
The sorted list.
Constraints
- 1 ≤ n ≤ 5 · 10^4
- -10^5 ≤ values ≤ 10^5
Merge sort fits linked lists well: split at the middle (slow/fast pointers), sort both halves, merge.
Example 1
Input
4 4 2 1 3
Output
1 2 3 4
Example 2
Input
5 -1 5 3 4 0
Output
-1 0 3 4 5
Hints
- Merge sort needs no random access, so it suits linked lists.
- Find the middle with slow/fast pointers, cut the list in two, sort each half recursively, then merge the two sorted halves.
Approach
sort(head): a list of 0 or 1 nodes is sorted. Otherwise find the node before the middle (fast starts one step ahead), cut there, sort both halves and merge them like "Merge Two Sorted Lists". The recursion depth is O(log n) and every level does O(n) merging work.
Complexity: O(n log n) time · O(log n) recursion depth
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
struct Node {
long long val;
Node *next = nullptr;
Node(long long v) : val(v) {}
};
Node *merge(Node *a, Node *b) {
Node dummy(0), *t = &dummy;
while (a && b) {
if (a->val <= b->val) t->next = a, a = a->next;
else t->next = b, b = b->next;
t = t->next;
}
t->next = a ? a : b;
return dummy.next;
}
Node *sortList(Node *head) {
if (!head || !head->next) return head;
Node *slow = head, *fast = head->next;
while (fast && fast->next) slow = slow->next, fast = fast->next->next;
Node *right = slow->next;
slow->next = nullptr;
return merge(sortList(head), sortList(right));
}
int main() {
int n;
cin >> n;
Node dummy(0), *t = &dummy;
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
t = t->next = new Node(x);
}
for (Node *p = sortList(dummy.next); p; p = p->next) cout << p->val << (p->next ? " " : "\n");
return 0;
}Python solution
import sys
class Node:
def __init__(self, val):
self.val, self.next = val, None
def merge(a, b):
dummy = t = Node(0)
while a and b:
if a.val <= b.val:
t.next, a = a, a.next
else:
t.next, b = b, b.next
t = t.next
t.next = a or b
return dummy.next
def sort_list(head):
if not head or not head.next:
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
return merge(sort_list(head), sort_list(right))
data = list(map(int, sys.stdin.read().split()))
dummy = tail = Node(0)
for v in data[1 : 1 + data[0]]:
tail.next = Node(v)
tail = tail.next
out, p = [], sort_list(dummy.next)
while p:
out.append(p.val)
p = p.next
print(*out)Java solution
import java.util.*;
import java.io.*;
public class Main {
static class Node {
long val;
Node next;
Node(long v) { val = v; }
}
static Node merge(Node a, Node b) {
Node dummy = new Node(0), t = dummy;
while (a != null && b != null) {
if (a.val <= b.val) { t.next = a; a = a.next; }
else { t.next = b; b = b.next; }
t = t.next;
}
t.next = a != null ? a : b;
return dummy.next;
}
static Node sortList(Node head) {
if (head == null || head.next == null) return head;
Node slow = head, fast = head.next;
while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
Node right = slow.next;
slow.next = null;
return merge(sortList(head), sortList(right));
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine().trim());
StringTokenizer st = new StringTokenizer(br.readLine());
Node dummy = new Node(0), t = dummy;
for (int i = 0; i < n; i++) t = t.next = new Node(Long.parseLong(st.nextToken()));
StringBuilder sb = new StringBuilder();
for (Node p = sortList(dummy.next); p != null; p = p.next) sb.append(p.val).append(p.next != null ? " " : "");
System.out.println(sb);
}
}