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
- 1 ≤ n ≤ 10^5
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
- Walk the list once, turning every next pointer around so it points to the previous node.
- 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);
}
}