Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Merge sort needs no random access, so it suits linked lists.
  2. 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);
    }
}

Solve Sort a Linked List online · All practice problems