Challenge: Turn the Train Around

Lab Java Intermediate 20 points

Read n numbers into a linked list (in order), reverse the list by changing the arrows (prev / cur / next), and print it.

Input

Line 1: n (n ≥ 1). Line 2: n whole numbers.

Output

The reversed list, separated by spaces.

Example

Input

5
1 2 3 4 5

Output

5 4 3 2 1

Sample input available Sample output available

Editor

Java

Hints

Build the list with head and tail.

Save next = cur.next before you change cur.next, or you lose the rest of the list.

Solution explanation

One pass, each arrow flipped once: O(n) time, O(1) extra memory.

Show solution

import java.util.Scanner;

class Node {
    int value;
    Node next;
    Node(int value) { this.value = value; }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Node head = null, tail = null;
        for (int i = 0; i < n; i++) {
            Node node = new Node(sc.nextInt());
            if (head == null) head = tail = node;
            else { tail.next = node; tail = node; }
        }
        Node prev = null, cur = head;
        while (cur != null) {
            Node next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        StringBuilder sb = new StringBuilder();
        for (Node c = prev; c != null; c = c.next) {
            if (c != prev) sb.append(' ');
            sb.append(c.value);
        }
        System.out.println(sb);
    }
}

Output

Answer