Getting everything ready for you…

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

0s

Practice › Linked List

Reverse a Linked List

Easy · Linked List · Asked at Amazon, Microsoft, Google, TCS, Infosys

Build a singly linked list from the values, reverse it, and print the values from the new head.

Input

First line: n. Second line: the n node values from head to tail.

Output

The reversed list, space-separated.

Constraints

Iteratively: keep prev, curr, next pointers. Try the recursive version too.

Example 1

Input

5
1 2 3 4 5

Output

5 4 3 2 1

Example 2

Input

1
7

Output

7

Hints

  1. Walk the list once, turning every next pointer around so it points to the previous node.
  2. Keep three pointers: prev (starts as null), curr, and next (saved before you overwrite curr.next).

Approach

Iterate with prev = null and curr = head. At each node: save next = curr.next, point curr.next = prev, then move both forward (prev = curr, curr = next). When curr is null, prev is the new head. Recursion also works but uses O(n) stack, which risks overflow at 10^5 nodes.

Complexity: O(n) time · O(1) extra space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

struct Node {
    long long val;
    Node *next;
    Node(long long v) : val(v), next(nullptr) {}
};

int main() {
    int n;
    cin >> n;
    Node dummy(0), *tail = &dummy;
    for (int i = 0; i < n; i++) {
        long long v;
        cin >> v;
        tail = tail->next = new Node(v);
    }
    Node *prev = nullptr, *curr = dummy.next;
    while (curr) {
        Node *next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    for (Node *p = prev; p; p = p->next) cout << p->val << (p->next ? " " : "\n");
    return 0;
}

Python solution

import sys


class Node:
    def __init__(self, val, nxt=None):
        self.val, self.next = val, nxt


data = sys.stdin.read().split()
n = int(data[0])
head = None
for v in reversed(data[1 : n + 1]):  # build the list from the tail backwards
    head = Node(v, head)

prev, curr = None, head
while curr:
    nxt = curr.next
    curr.next = prev
    prev, curr = curr, nxt

out = []
while prev:
    out.append(prev.val)
    prev = prev.next
print(" ".join(out))

Java solution

import java.util.*;

public class Main {
    static class Node {
        long val;
        Node next;
        Node(long v) { val = v; }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Node dummy = new Node(0), tail = dummy;
        for (int i = 0; i < n; i++) tail = tail.next = new Node(sc.nextLong());
        Node prev = null, curr = dummy.next;
        while (curr != null) {
            Node next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        StringBuilder sb = new StringBuilder();
        for (Node p = prev; p != null; p = p.next) sb.append(p.val).append(p.next != null ? " " : "");
        System.out.println(sb);
    }
}

Solve Reverse a Linked List online · All practice problems