Linked List Reversal
In this page:
Idea of Reversal
Reversing a linked list means flipping every node's next pointer so it points to the node that came before it instead of the one that came after, which effectively turns the whole chain around.
Example: Idea of Reversal
#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
Node* a = new Node{1, nullptr};
Node* b = new Node{2, nullptr};
Node* c = new Node{3, nullptr};
a->next = b; b->next = c;
cout << "before: " << a->data << "->" << b->data << "->" << c->data << endl;
c->next = b; b->next = a; a->next = nullptr;
cout << "after: " << c->data << "->" << b->data << "->" << a->data << endl;
return 0;
}class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
public static void main(String[] args) {
Node a = new Node(1), b = new Node(2), c = new Node(3);
a.next = b; b.next = c;
System.out.println("before: " + a.data + "->" + b.data + "->" + c.data);
c.next = b; b.next = a; a.next = null;
System.out.println("after: " + c.data + "->" + b.data + "->" + a.data);
}
}class Node:
def __init__(self, data):
self.data = data
self.next = None
a, b, c = Node(1), Node(2), Node(3)
a.next = b
b.next = c
print("before:", a.data, "->", b.data, "->", c.data)
c.next = b
b.next = a
a.next = None
print("after:", c.data, "->", b.data, "->", a.data)#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int main() {
struct Node *a = malloc(sizeof(struct Node));
struct Node *b = malloc(sizeof(struct Node));
struct Node *c = malloc(sizeof(struct Node));
a->data = 1; b->data = 2; c->data = 3;
a->next = b; b->next = c; c->next = NULL;
printf("before: %d->%d->%d\n", a->data, b->data, c->data);
c->next = b; b->next = a; a->next = NULL;
printf("after: %d->%d->%d\n", c->data, b->data, a->data);
return 0;
}Login to try C/C++/Java code in the editor
Iterative Method
The iterative method walks through the list once, and at each node redirects its next pointer to point backward to the previous node, carefully saving a reference to the next node first so the rest of the list isn't lost.
Example: Iterative Method
#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
Node* reverseList(Node* head) {
Node* prev = nullptr;
while (head != nullptr) {
Node* nextNode = head->next;
head->next = prev;
prev = head;
head = nextNode;
}
return prev;
}
int main() {
Node* a = new Node{1, new Node{2, new Node{3, nullptr}}};
Node* newHead = reverseList(a);
for (Node* c = newHead; c; c = c->next) cout << c->data << " ";
cout << endl;
return 0;
}class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
static Node reverseList(Node head) {
Node prev = null;
while (head != null) {
Node nextNode = head.next;
head.next = prev;
prev = head;
head = nextNode;
}
return prev;
}
public static void main(String[] args) {
Node a = new Node(1); a.next = new Node(2); a.next.next = new Node(3);
Node newHead = reverseList(a);
for (Node c = newHead; c != null; c = c.next) System.out.print(c.data + " ");
}
}class Node:
def __init__(self, data):
self.data = data
self.next = None
def reverse_list(head):
prev = None
while head is not None:
next_node = head.next
head.next = prev
prev = head
head = next_node
return prev
a = Node(1); a.next = Node(2); a.next.next = Node(3)
new_head = reverse_list(a)
c = new_head
while c:
print(c.data, end=" ")
c = c.next#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
struct Node* reverseList(struct Node *head) {
struct Node *prev = NULL;
while (head != NULL) {
struct Node *nextNode = head->next;
head->next = prev;
prev = head;
head = nextNode;
}
return prev;
}
int main() {
struct Node *a = malloc(sizeof(struct Node)); a->data = 1;
struct Node *b = malloc(sizeof(struct Node)); b->data = 2;
struct Node *c = malloc(sizeof(struct Node)); c->data = 3; c->next = NULL;
a->next = b; b->next = c;
struct Node *newHead = reverseList(a);
for (struct Node *n = newHead; n; n = n->next) printf("%d ", n->data);
printf("\n");
return 0;
}Login to try C/C++/Java code in the editor
Pointer Steps
Three pointers make the logic manageable: one for the previous node, one for the current node being processed, and one temporary pointer to remember the next node before you overwrite current's pointer.
Example: Pointer Steps
#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
Node* head = new Node{1, new Node{2, new Node{3, nullptr}}};
Node* prevNode = nullptr;
Node* curr = head;
while (curr != nullptr) {
Node* nextNode = curr->next;
cout << "curr=" << curr->data << " prev=" << (prevNode ? to_string(prevNode->data) : "null") << endl;
curr->next = prevNode;
prevNode = curr;
curr = nextNode;
}
return 0;
}class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
public static void main(String[] args) {
Node head = new Node(1); head.next = new Node(2); head.next.next = new Node(3);
Node prevNode = null, curr = head;
while (curr != null) {
Node nextNode = curr.next;
System.out.println("curr=" + curr.data + " prev=" + (prevNode == null ? "null" : prevNode.data));
curr.next = prevNode;
prevNode = curr;
curr = nextNode;
}
}
}class Node:
def __init__(self, data):
self.data = data
self.next = None
head = Node(1); head.next = Node(2); head.next.next = Node(3)
prev_node, curr = None, head
while curr is not None:
next_node = curr.next
print("curr=", curr.data, "prev=", prev_node.data if prev_node else "None")
curr.next = prev_node
prev_node = curr
curr = next_node#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int main() {
struct Node *a = malloc(sizeof(struct Node)); a->data = 1;
struct Node *b = malloc(sizeof(struct Node)); b->data = 2;
struct Node *c = malloc(sizeof(struct Node)); c->data = 3; c->next = NULL;
a->next = b; b->next = c;
struct Node *prevNode = NULL, *curr = a;
while (curr != NULL) {
struct Node *nextNode = curr->next;
printf("curr=%d prev=%d\n", curr->data, prevNode ? prevNode->data : -1);
curr->next = prevNode;
prevNode = curr;
curr = nextNode;
}
return 0;
}Login to try C/C++/Java code in the editor
Result
Once the reversal finishes, the node that used to be the tail (with a null next pointer) is now the head of the list, since it was the last node processed and its next pointer was set to point at the second-to-last node.
Example: Result
#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
Node* reverseList(Node* head) {
Node* prev = nullptr;
while (head) { Node* nx = head->next; head->next = prev; prev = head; head = nx; }
return prev;
}
int main() {
Node* a = new Node{1, new Node{2, new Node{3, nullptr}}};
Node* oldTail = a;
while (oldTail->next) oldTail = oldTail->next;
Node* newHead = reverseList(a);
cout << "old tail is now head: " << (newHead == oldTail) << endl;
return 0;
}class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
static Node reverseList(Node head) {
Node prev = null;
while (head != null) { Node nx = head.next; head.next = prev; prev = head; head = nx; }
return prev;
}
public static void main(String[] args) {
Node a = new Node(1); a.next = new Node(2); a.next.next = new Node(3);
Node oldTail = a;
while (oldTail.next != null) oldTail = oldTail.next;
Node newHead = reverseList(a);
System.out.println("old tail is now head: " + (newHead == oldTail));
}
}class Node:
def __init__(self, data):
self.data = data
self.next = None
def reverse_list(head):
prev = None
while head:
nx = head.next
head.next = prev
prev = head
head = nx
return prev
a = Node(1); a.next = Node(2); a.next.next = Node(3)
old_tail = a
while old_tail.next:
old_tail = old_tail.next
new_head = reverse_list(a)
print("old tail is now head:", new_head is old_tail)#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
struct Node* reverseList(struct Node *head) {
struct Node *prev = NULL;
while (head) { struct Node *nx = head->next; head->next = prev; prev = head; head = nx; }
return prev;
}
int main() {
struct Node *a = malloc(sizeof(struct Node)); a->data = 1;
struct Node *b = malloc(sizeof(struct Node)); b->data = 2;
struct Node *c = malloc(sizeof(struct Node)); c->data = 3; c->next = NULL;
a->next = b; b->next = c;
struct Node *oldTail = a;
while (oldTail->next) oldTail = oldTail->next;
struct Node *newHead = reverseList(a);
printf("old tail is now head: %d\n", newHead == oldTail);
return 0;
}Login to try C/C++/Java code in the editor
Complexity
The iterative approach reverses the whole list in a single O(n) pass while using only a fixed handful of pointer variables, so it needs O(1) extra space, unlike a recursive version which uses O(n) stack space.
Example: Complexity
#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
Node* reverseList(Node* head) {
Node* prev = nullptr;
while (head) { Node* nx = head->next; head->next = prev; prev = head; head = nx; }
return prev;
}
int main() {
Node* a = new Node{1, new Node{2, new Node{3, nullptr}}};
Node* r = reverseList(a);
cout << "reversed in O(n) time, O(1) extra space (just prev/curr/next pointers)" << endl;
for (Node* c = r; c; c = c->next) cout << c->data << " ";
return 0;
}class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
static Node reverseList(Node head) {
Node prev = null;
while (head != null) { Node nx = head.next; head.next = prev; prev = head; head = nx; }
return prev;
}
public static void main(String[] args) {
Node a = new Node(1); a.next = new Node(2); a.next.next = new Node(3);
Node r = reverseList(a);
System.out.println("reversed in O(n) time, O(1) extra space (just prev/curr/next pointers)");
for (Node c = r; c != null; c = c.next) System.out.print(c.data + " ");
}
}class Node:
def __init__(self, data):
self.data = data
self.next = None
def reverse_list(head):
prev = None
while head:
nx = head.next
head.next = prev
prev = head
head = nx
return prev
a = Node(1); a.next = Node(2); a.next.next = Node(3)
r = reverse_list(a)
print("reversed in O(n) time, O(1) extra space (just prev/curr/next pointers)")
c = r
while c:
print(c.data, end=" ")
c = c.next#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
struct Node* reverseList(struct Node *head) {
struct Node *prev = NULL;
while (head) { struct Node *nx = head->next; head->next = prev; prev = head; head = nx; }
return prev;
}
int main() {
struct Node *a = malloc(sizeof(struct Node)); a->data = 1;
struct Node *b = malloc(sizeof(struct Node)); b->data = 2;
struct Node *c = malloc(sizeof(struct Node)); c->data = 3; c->next = NULL;
a->next = b; b->next = c;
struct Node *r = reverseList(a);
printf("reversed in O(n) time, O(1) extra space\n");
for (struct Node *n = r; n; n = n->next) printf("%d ", n->data);
return 0;
}Login to try C/C++/Java code in the editor
🔒
Chapter Quiz — Complete all 8 topics to unlock
0/8 topics done
Complete these topics first: