Given a pointer to the head node of a linked list, the task is to reverse the linked list. We need to reverse the list by changing the links between nodes.
Examples:
Input: Head of following linked list
1->2->3->4->NULL
Output: Linked list should be changed to,
4->3->2->1->NULL
Input: Head of following linked list
1->2->3->4->5->NULL
Output: Linked list should be changed to,
5->4->3->2->1->NULL
Input: NULL
Output: NULL
Input: 1->NULL
Output: 1->NULL
Reverse a linked list by Iterative Method:
The idea is to use three pointers curr, prev, and next to keep track of nodes to update reverse links.
Illustration:
Follow the steps below to solve the problem:
- Initialize three pointers prev as NULL, curr as head, and next as NULL.
- Iterate through the linked list. In a loop, do the following:
- Before changing the next of curr, store the next node
- Now update the next pointer of curr to the prev
- Update prev as curr and curr as next
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
Node(int data)
{
this->data = data;
next = NULL;
}
};
struct LinkedList {
Node* head;
LinkedList() { head = NULL; }
void reverse()
{
Node* current = head;
Node *prev = NULL, *next = NULL;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
head = prev;
}
void print()
{
struct Node* temp = head;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
}
void push(int data)
{
Node* temp = new Node(data);
temp->next = head;
head = temp;
}
};
int main()
{
LinkedList ll;
ll.push(20);
ll.push(4);
ll.push(15);
ll.push(85);
cout << "Given linked list\n";
ll.print();
ll.reverse();
cout << "\nReversed linked list \n";
ll.print();
return 0;
}
|
C
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
static void reverse(struct Node** head_ref)
{
struct Node* prev = NULL;
struct Node* current = *head_ref;
struct Node* next = NULL;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*head_ref = prev;
}
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node
= (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
void printList(struct Node* head)
{
struct Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
}
int main()
{
struct Node* head = NULL;
push(&head, 20);
push(&head, 4);
push(&head, 15);
push(&head, 85);
printf("Given linked list\n");
printList(head);
reverse(&head);
printf("\nReversed linked list \n");
printList(head);
getchar();
}
|
Java
class LinkedList {
static Node head;
static class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
Node reverse(Node node)
{
Node prev = null;
Node current = node;
Node next = null;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
node = prev;
return node;
}
void printList(Node node)
{
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}
public static void main(String[] args)
{
LinkedList list = new LinkedList();
list.head = new Node(85);
list.head.next = new Node(15);
list.head.next.next = new Node(4);
list.head.next.next.next = new Node(20);
System.out.println("Given linked list");
list.printList(head);
head = list.reverse(head);
System.out.println("");
System.out.println("Reversed linked list ");
list.printList(head);
}
}
|
Python3
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def reverse(self):
prev = None
current = self.head
while(current is not None):
next = current.next
current.next = prev
prev = current
current = next
self.head = prev
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
def printList(self):
temp = self.head
while(temp):
print(temp.data, end=" ")
temp = temp.next
llist = LinkedList()
llist.push(20)
llist.push(4)
llist.push(15)
llist.push(85)
print ("Given linked list")
llist.printList()
llist.reverse()
print ("\nReversed linked list")
llist.printList()
|
C#
using System;
class GFG {
static void Main(string[] args)
{
LinkedList list = new LinkedList();
list.AddNode(new LinkedList.Node(85));
list.AddNode(new LinkedList.Node(15));
list.AddNode(new LinkedList.Node(4));
list.AddNode(new LinkedList.Node(20));
Console.WriteLine("Given linked list ");
list.PrintList();
list.ReverseList();
Console.WriteLine("Reversed linked list ");
list.PrintList();
}
}
class LinkedList {
Node head;
public class Node {
public int data;
public Node next;
public Node(int d)
{
data = d;
next = null;
}
}
public void AddNode(Node node)
{
if (head == null)
head = node;
else {
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = node;
}
}
public void ReverseList()
{
Node prev = null, current = head, next = null;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
head = prev;
}
public void PrintList()
{
Node current = head;
while (current != null) {
Console.Write(current.data + " ");
current = current.next;
}
Console.WriteLine();
}
}
|
Javascript
<script>
var head;
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
function reverse(node) {
var prev = null;
var current = node;
var next = null;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
node = prev;
return node;
}
function printList(node) {
while (node != null) {
document.write(node.data + " ");
node = node.next;
}
}
head = new Node(85);
head.next = new Node(15);
head.next.next = new Node(4);
head.next.next.next = new Node(20);
document.write("Given linked list<br/>");
printList(head);
head = reverse(head);
document.write("<br/>");
document.write("Reversed linked list<br/> ");
printList(head);
</script>
|
Output
Given linked list
85 15 4 20
Reversed linked list
20 4 15 85
Time Complexity: O(N), Traversing over the linked list of size N.
Auxiliary Space: O(1)
Reverse a linked list using Recursion:
The idea is to reach the last node of the linked list using recursion then start reversing the linked list.
Illustration:
Follow the steps below to solve the problem:
- Divide the list in two parts – first node and rest of the linked list.
- Call reverse for the rest of the linked list.
- Link the rest linked list to first.
- Fix head pointer to NULL
Below is the implementation of above approach:
C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
Node(int data)
{
this->data = data;
next = NULL;
}
};
struct LinkedList {
Node* head;
LinkedList() { head = NULL; }
Node* reverse(Node* head)
{
if (head == NULL || head->next == NULL)
return head;
Node* rest = reverse(head->next);
head->next->next = head;
head->next = NULL;
return rest;
}
void print()
{
struct Node* temp = head;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
}
void push(int data)
{
Node* temp = new Node(data);
temp->next = head;
head = temp;
}
};
int main()
{
LinkedList ll;
ll.push(20);
ll.push(4);
ll.push(15);
ll.push(85);
cout << "Given linked list\n";
ll.print();
ll.head = ll.reverse(ll.head);
cout << "\nReversed linked list \n";
ll.print();
return 0;
}
|
Java
import java.io.*;
class recursion {
static Node head;
static class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
static Node reverse(Node head)
{
if (head == null || head.next == null)
return head;
Node rest = reverse(head.next);
head.next.next = head;
head.next = null;
return rest;
}
static void print()
{
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
static void push(int data)
{
Node temp = new Node(data);
temp.next = head;
head = temp;
}
public static void main(String args[])
{
push(20);
push(4);
push(15);
push(85);
System.out.println("Given linked list");
print();
head = reverse(head);
System.out.println("Reversed linked list");
print();
}
}
|
Python3
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def reverse(self, head):
if head is None or head.next is None:
return head
rest = self.reverse(head.next)
head.next.next = head
head.next = None
return rest
def __str__(self):
linkedListStr = ""
temp = self.head
while temp:
linkedListStr = (linkedListStr +
str(temp.data) + " ")
temp = temp.next
return linkedListStr
def push(self, data):
temp = Node(data)
temp.next = self.head
self.head = temp
linkedList = LinkedList()
linkedList.push(20)
linkedList.push(4)
linkedList.push(15)
linkedList.push(85)
print("Given linked list")
print(linkedList)
linkedList.head = linkedList.reverse(linkedList.head)
print("Reversed linked list")
print(linkedList)
|
C#
using System;
class recursion {
static Node head;
public class Node {
public int data;
public Node next;
public Node(int d)
{
data = d;
next = null;
}
}
static Node reverse(Node head)
{
if (head == null || head.next == null)
return head;
Node rest = reverse(head.next);
head.next.next = head;
head.next = null;
return rest;
}
static void print()
{
Node temp = head;
while (temp != null) {
Console.Write(temp.data + " ");
temp = temp.next;
}
Console.WriteLine();
}
static void push(int data)
{
Node temp = new Node(data);
temp.next = head;
head = temp;
}
public static void Main(String[] args)
{
push(20);
push(4);
push(15);
push(85);
Console.WriteLine("Given linked list");
print();
head = reverse(head);
Console.WriteLine("Reversed linked list");
print();
}
}
|
Javascript
<script>
var head;
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
function reverse(head) {
if (head == null || head.next == null)
return head;
var rest = reverse(head.next);
head.next.next = head;
head.next = null;
return rest;
}
function print() {
var temp = head;
while (temp != null) {
document.write(temp.data + " ");
temp = temp.next;
}
document.write();
}
function push(data) {
var temp = new Node(data);
temp.next = head;
head = temp;
}
push(20);
push(4);
push(15);
push(85);
document.write("Given linked list<br/>");
print();
head = reverse(head);
document.write("<br/>Reversed Linked list<br/>");
print();
</script>
|
Output
Given linked list
85 15 4 20
Reversed linked list
20 4 15 85
Time Complexity: O(N), Visiting over every node one time
Auxiliary Space: O(N), Function call stack space
Reverse a linked list by Tail Recursive Method:
The idea is to maintain three pointers previous, current and next, recursively visit every node and make links using these three pointers.
Follow the steps below to solve the problem:
- First update next with next node of current i.e. next = current->next
- Now make a reverse link from current node to previous node i.e. curr->next = prev
- If the visited node is the last node then just make a reverse link from the current node to previous node and update head.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
void reverseUtil(Node* curr, Node* prev, Node** head);
void reverse(Node** head)
{
if (!head)
return;
reverseUtil(*head, NULL, head);
}
void reverseUtil(Node* curr, Node* prev, Node** head)
{
if (!curr->next) {
*head = curr;
curr->next = prev;
return;
}
Node* next = curr->next;
curr->next = prev;
reverseUtil(next, curr, head);
}
Node* newNode(int key)
{
Node* temp = new Node;
temp->data = key;
temp->next = NULL;
return temp;
}
void printlist(Node* head)
{
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
cout << endl;
}
int main()
{
Node* head1 = newNode(1);
head1->next = newNode(2);
head1->next->next = newNode(3);
head1->next->next->next = newNode(4);
head1->next->next->next->next = newNode(5);
head1->next->next->next->next->next = newNode(6);
head1->next->next->next->next->next->next = newNode(7);
head1->next->next->next->next->next->next->next
= newNode(8);
cout << "Given linked list\n";
printlist(head1);
reverse(&head1);
cout << "Reversed linked list\n";
printlist(head1);
return 0;
}
|
C
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
void reverseUtil(Node* curr, Node* prev, Node** head);
void reverse(Node** head)
{
if (!head)
return;
reverseUtil(*head, NULL, head);
}
void reverseUtil(Node* curr, Node* prev, Node** head)
{
if (!curr->next) {
*head = curr;
curr->next = prev;
return;
}
Node* next = curr->next;
curr->next = prev;
reverseUtil(next, curr, head);
}
Node* newNode(int key)
{
Node* temp = (Node*)malloc(sizeof(Node));
temp->data = key;
temp->next = NULL;
return temp;
}
void printlist(Node* head)
{
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
printf("\n");
}
int main()
{
Node* head1 = newNode(1);
head1->next = newNode(2);
head1->next->next = newNode(3);
head1->next->next->next = newNode(4);
head1->next->next->next->next = newNode(5);
head1->next->next->next->next->next = newNode(6);
head1->next->next->next->next->next->next = newNode(7);
head1->next->next->next->next->next->next->next
= newNode(8);
printf("Given linked list\n");
printlist(head1);
reverse(&head1);
printf("Reversed linked list\n");
printlist(head1);
return 0;
}
|
Java
class LinkedList {
static Node head;
static class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
Node reverseUtil(Node curr, Node prev)
{
if (head == null)
return head;
if (curr.next == null) {
head = curr;
curr.next = prev;
return head;
}
Node next1 = curr.next;
curr.next = prev;
reverseUtil(next1, curr);
return head;
}
void printList(Node node)
{
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}
public static void main(String[] args)
{
LinkedList list = new LinkedList();
list.head = new Node(1);
list.head.next = new Node(2);
list.head.next.next = new Node(3);
list.head.next.next.next = new Node(4);
list.head.next.next.next.next = new Node(5);
list.head.next.next.next.next.next = new Node(6);
list.head.next.next.next.next.next.next
= new Node(7);
list.head.next.next.next.next.next.next.next
= new Node(8);
System.out.println("Given linked list ");
list.printList(head);
Node res = list.reverseUtil(head, null);
System.out.println("\nReversed linked list ");
list.printList(res);
}
}
|
Python3
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def reverseUtil(self, curr, prev):
if curr.next is None:
self.head = curr
curr.next = prev
return
next = curr.next
curr.next = prev
self.reverseUtil(next, curr)
def reverse(self):
if self.head is None:
return
self.reverseUtil(self.head, None)
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
def printList(self):
temp = self.head
while(temp):
print (temp.data, end=" ")
temp = temp.next
llist = LinkedList()
llist.push(8)
llist.push(7)
llist.push(6)
llist.push(5)
llist.push(4)
llist.push(3)
llist.push(2)
llist.push(1)
print ("Given linked list")
llist.printList()
llist.reverse()
print ("\nReversed linked list")
llist.printList()
|
C#
using System;
public class LinkedList {
Node head;
public class Node {
public int data;
public Node next;
public Node(int d)
{
data = d;
next = null;
}
}
Node reverseUtil(Node curr, Node prev)
{
if (curr.next == null) {
head = curr;
curr.next = prev;
return head;
}
Node next1 = curr.next;
curr.next = prev;
reverseUtil(next1, curr);
return head;
}
void printList(Node node)
{
while (node != null) {
Console.Write(node.data + " ");
node = node.next;
}
}
public static void Main(String[] args)
{
LinkedList list = new LinkedList();
list.head = new Node(1);
list.head.next = new Node(2);
list.head.next.next = new Node(3);
list.head.next.next.next = new Node(4);
list.head.next.next.next.next = new Node(5);
list.head.next.next.next.next.next = new Node(6);
list.head.next.next.next.next.next.next
= new Node(7);
list.head.next.next.next.next.next.next.next
= new Node(8);
Console.WriteLine("Given linked list ");
list.printList(list.head);
Node res = list.reverseUtil(list.head, null);
Console.WriteLine("\nReversed linked list ");
list.printList(res);
}
}
|
Javascript
<script>
var head;
class Node {
constructor(d) {
this.data = d;
this.next = null;
}
}
function reverseUtil(curr, prev)
{
if (head == null)
return head;
if (curr.next == null) {
head = curr;
curr.next = prev;
return head;
}
var next1 = curr.next;
curr.next = prev;
reverseUtil(next1, curr);
return head;
}
function printList(node) {
while (node != null) {
document.write(node.data + " ");
node = node.next;
}
}
var head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
head.next.next.next.next = new Node(5);
head.next.next.next.next.next = new Node(6);
head.next.next.next.next.next.next = new Node(7);
head.next.next.next.next.next.next.next = new Node(8);
document.write("Original Linked list<br/> ");
printList(head);
var res = reverseUtil(head, null);
document.write("<br/>");
document.write("Reversed linked list <br/>");
printList(res);
</script>
|
Output
Given linked list
1 2 3 4 5 6 7 8
Reversed linked list
8 7 6 5 4 3 2 1
Time Complexity: O(N), Visiting every node of the linked list of size N.
Auxiliary Space: O(N), Function call stack space
Reverse a linked list using Stack:
The idea is to store the all the nodes in the stack then make a reverse linked list.
Follow the steps below to solve the problem:
- Store the nodes(values and address) in the stack until all the values are entered.
- Once all entries are done, Update the Head pointer to the last location(i.e the last value).
- Start popping the nodes(value and address) and store them in the same order until the stack is empty.
- Update the next pointer of last Node in the stack by NULL.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* next;
};
void reverseLL(Node** head)
{
stack<Node*> s;
Node* temp = *head;
while (temp->next != NULL) {
s.push(temp);
temp = temp->next;
}
*head = temp;
while (!s.empty()) {
temp->next = s.top();
s.pop();
temp = temp->next;
}
temp->next = NULL;
}
void printlist(Node* temp)
{
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
}
void insert_back(Node** head, int value)
{
Node* temp = new Node();
temp->data = value;
temp->next = NULL;
if (*head == NULL) {
*head = temp;
return;
}
else {
Node* last_node = *head;
while (last_node->next != NULL)
last_node = last_node->next;
last_node->next = temp;
return;
}
}
int main()
{
Node* head = NULL;
insert_back(&head, 1);
insert_back(&head, 2);
insert_back(&head, 3);
insert_back(&head, 4);
cout << "Given linked list\n";
printlist(head);
reverseLL(&head);
cout << "\nReversed linked list\n";
printlist(head);
return 0;
}
|
Java
import java.util.*;
class GFG {
static class Node {
int data;
Node next;
};
static Node head = null;
static void reverseLL()
{
Stack<Node> s = new Stack<>();
Node temp = head;
while (temp.next != null) {
s.add(temp);
temp = temp.next;
}
head = temp;
while (!s.isEmpty()) {
temp.next = s.peek();
s.pop();
temp = temp.next;
}
temp.next = null;
}
static void printlist(Node temp)
{
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
}
static void insert_back(int value)
{
Node temp = new Node();
temp.data = value;
temp.next = null;
if (head == null) {
head = temp;
return;
}
else {
Node last_node = head;
while (last_node.next != null)
last_node = last_node.next;
last_node.next = temp;
return;
}
}
public static void main(String[] args)
{
insert_back(1);
insert_back(2);
insert_back(3);
insert_back(4);
System.out.print("Given linked list\n");
printlist(head);
reverseLL();
System.out.print("\nReversed linked list\n");
printlist(head);
}
}
|
Python3
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reverseLLUsingStack(self, head):
stack, temp = [], head
while temp:
stack.append(temp)
temp = temp.next
head = temp = stack.pop()
while len(stack) > 0:
temp.next = stack.pop()
temp = temp.next
temp.next = None
return head
if __name__ == "__main__":
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
print("Given linked list")
temp = head
while temp:
print(temp.val, end=' ')
temp = temp.next
obj = Solution()
print("\nReversed linked list")
head = obj.reverseLLUsingStack(head)
while head:
print(head.val, end=' ')
head = head.next
|
C#
using System;
using System.Collections.Generic;
class GFG {
public class Node {
public int data;
public Node next;
};
static Node head = null;
static void reverseLL()
{
Stack<Node> s = new Stack<Node>();
Node temp = head;
while (temp.next != null) {
s.Push(temp);
temp = temp.next;
}
head = temp;
while (s.Count != 0) {
temp.next = s.Peek();
s.Pop();
temp = temp.next;
}
temp.next = null;
}
static void printlist(Node temp)
{
while (temp != null) {
Console.Write(temp.data + " ");
temp = temp.next;
}
}
static void insert_back(int value)
{
Node temp = new Node();
temp.data = value;
temp.next = null;
if (head == null) {
head = temp;
return;
}
else {
Node last_node = head;
while (last_node.next != null) {
last_node = last_node.next;
}
last_node.next = temp;
return;
}
}
public static void Main(String[] args)
{
insert_back(1);
insert_back(2);
insert_back(3);
insert_back(4);
Console.Write("Given linked list\n");
printlist(head);
reverseLL();
Console.Write("\nReversed linked list\n");
printlist(head);
}
}
|
Javascript
<script>
class Node
{
constructor(){
this.data = 0;
this.next = null;
}
}
var head = null;
function reverseLL()
{
var s = [];
var temp = head;
while (temp.next != null)
{
s.push(temp);
temp = temp.next;
}
head = temp;
while (s.length!=0)
{
temp.next = s.pop();
temp = temp.next;
}
temp.next = null;
}
function printlist(temp)
{
while (temp != null)
{
document.write(temp.data+ " ");
temp = temp.next;
}
}
function insert_back( value)
{
var temp = new Node();
temp.data = value;
temp.next = null;
if (head == null)
{
head = temp;
return;
}
else
{
var last_node = head;
while (last_node.next != null)
{
last_node = last_node.next;
}
last_node.next = temp;
return;
}
}
insert_back(1);
insert_back(2);
insert_back(3);
insert_back(4);
document.write("Given linked list\n");
printlist(head);
reverseLL();
document.write("<br/>Reversed linked list\n");
printlist(head);
</script>
|
Output
Given linked list
1 2 3 4
Reversed linked list
4 3 2 1
Time Complexity: O(N), Visiting every node of the linked list of size N.
Auxiliary Space: O(N), Space is used to store the nodes in the stack.
Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!