Challenge: Reverse a Linked List

Lab C++ Intermediate 20 points

Build a linked list from the input, reverse it by changing the pointers, and print the values from the new head, separated by spaces.

Input

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

Output

The values in reversed order.

Example

Input

4
1 2 3 4

Output

4 3 2 1

Sample input available Sample output available

Editor

C++

Hints

prev = nullptr, cur = head.

Save cur->next, point cur->next at prev, then move prev and cur forward.

Solution explanation

Each pointer is turned around once: O(n) time, O(1) extra memory.

Show solution

#include <iostream>
using namespace std;

struct Node {
    int value;
    Node* next;
    Node(int v) : value(v), next(nullptr) {}
};

int main() {
    int n;
    cin >> n;
    Node* head = nullptr;
    Node* tail = nullptr;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        Node* node = new Node(x);
        if (!head) head = tail = node;
        else { tail->next = node; tail = node; }
    }
    Node* prev = nullptr;
    Node* cur = head;
    while (cur) {
        Node* nxt = cur->next;
        cur->next = prev;
        prev = cur;
        cur = nxt;
    }
    for (Node* c = prev; c; c = c->next) cout << c->value << (c->next ? " " : "\n");
    return 0;
}

Output

Answer