Reverse a linked list

Difficulty Level Easy
Frequently asked in Accolite Adobe Amazon MakeMyTrip Microsoft Qualcomm Samsung SAP SAP Labs Snapdeal Zoho

Problem Statement

The problem “reverse a linked list” states that we are given the head of the linked list. We have to reverse the linked list by changing the links between them and return the head of the reversed linked list.

Example

`10->20->30->40->NULL`
`NULL<-10<-20<-30<-40`

Explanation

We have reversed the linked list by changing the links between them. So the new linked list after performing reverse operation becomes 40->30->20->10->NULL.

Approach for reverse a linked list

Iterative approach

1. Initialize the current pointer as the head.
2. Initialize previous and the next pointer as NULL.
3. Run a loop till current points to NULL.
1. Assign current’s next to the next pointer.
2. Now assign the previous pointer to current’s next pointer.
3. Assign current to previous next to current.
4. Assign head to previous.

C++ code

```#include <iostream>
using namespace std;
struct Node {
int data;
struct Node* next;
Node(int data)
{
this->data = data;
next = NULL;
}
};
{
}
void reverse()
{
Node* current = head;
Node *prev = NULL, *next = NULL;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
}
void print()
{
struct Node* temp = head;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
}
void push(int data)
{
Node* temp = new Node(data);
}
};
int main()
{
ll.push(40);
ll.push(30);
ll.push(20);
ll.push(10);
cout << "old linked list\n";
ll.print();
ll.reverse();
cout << "\nnew Linked list \n";
ll.print();
return 0;
}
```
```old linked list:
10 20 30 40

40 30 20 10```

Java code

```class LinkedList {
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)
{
list.head = new Node(10);
list.head.next = new Node(20);
list.head.next.next = new Node(30);
list.head.next.next.next = new Node(40);
System.out.println("");
System.out.println("new linked list ");
}
}
```
```old linked list:
10 20 30 40

40 30 20 10```

Complexity Analysis

Time Complexity

O(n) because we are traversing the linked list only once.

Space Complexity

O(1) because we are using space to store temporary variables only.

Recursive approach

• We assign the last node as a head node by traversing through the linked list.
• And link the last returned tail of the linked list with its previous node. This step is followed by recursively.

C++ code

```#include <iostream>
using namespace std;
struct Node {
int data;
struct Node* next;
Node(int data)
{
this->data = data;
next = NULL;
}
};
{
}
Node* reverse(Node* node)
{
if (node == NULL)
return NULL;
if (node->next == NULL) {
return node;
}
Node* node1 = reverse(node->next);
node1->next = node;
node->next = NULL;
return node;
}
/* Function to print linked list */
void print()
{
struct Node* temp = head;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
}
void push(int data)
{
Node* temp = new Node(data);
}
};
int main()
{
ll.push(40);
ll.push(30);
ll.push(20);
ll.push(10);
cout << "old linked list\n";
ll.print();
cout << "\n new Linked list \n";
ll.print();
return 0;
}
```
```old linked list:
10 20 30 40

40 30 20 10```

Java code to reverse a linked list

```import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Scanner;
static class Node {
public int data;
public Node next;
public Node(int nodeData) {
this.data = nodeData;
this.next = null;
}
}
static class LinkedList {
}
public void insertNode(int nodeData) {
Node node = new Node(nodeData);
if (this.head != null) {
}
}
}
public static void printSinglyLinkedList(Node node,
String sep) throws IOException {
while (node != null) {
System.out.print(String.valueOf(node.data) + sep);
node = node.next;
}
}
static Node reverse(Node head) {
if(head == null) {
}
if(head.next == null) {
}
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {

llist.insertNode(40);
llist.insertNode(30);
llist.insertNode(20);
llist.insertNode(10);

System.out.println();
Node llist1 = reverse(llist.head);
scanner.close();
}
}
```
```old linked list:
10 20 30 40

40 30 20 10```

Complexity Analysis

Time Complexity

O(n) because we are traversing the linked list only once.

Space Complexity

O(n) because we are using space to store temporary variables on the compiler stack. These temporary variables are dependent on the number of nodes in the linked list.

Tail recursive approach

This approach is a type of recursion which is also known as tail recursion. In the tail recursion, we need not go back to the function which has initiated its call. We pass the result values of the previous call as a parameter to the new function call. This is useful at the compiler level also because we need not maintain the system stack to store the values of previous calls. This is also helpful in preventing from stack overflow.

C++ code

```#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
void reverseUtil(Node* curr, Node* prev, Node** head);
{
return;
}
void reverseUtil(Node* curr, Node* prev, Node** head)
{
if (!curr->next) {
curr->next = prev;
return;
}
Node* next = curr->next;
curr->next = prev;
}
Node* newNode(int key)
{
Node* temp = new Node;
temp->data = key;
temp->next = NULL;
return temp;
}
{
while (head != NULL) {
cout << head->data << " ";
}
cout << endl;
}
int main()
{
Node* head1 = newNode(1);
cout << "old linked list\n";
cout << "\nnew linked list\n";
return 0;
}
```
```old linked list
1 2 3 4 5 6 7 8

8 7 6 5 4 3 2 1```

Java code

```class LinkedList {
static class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
Node reverseUtil(Node curr, Node prev)
{
if (curr.next == null) {
curr.next = prev;
}
Node next1 = curr.next;
curr.next = prev;
reverseUtil(next1, curr);
}
void printList(Node node)
{
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}
public static void main(String[] args)
{
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("Old Linked list ");
Node res = list.reverseUtil(head, null);
System.out.println("");
System.out.println("");
System.out.println("new linked list ");
list.printList(res);
}
}
```
```old linked list
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1```

Complexity Analysis

Time Complexity

O(n) because we are traversing the linked list only once.

Space Complexity

O(n) because we are using space to store temporary variables only on the compiler stack. These temporary variables are dependent on the number of nodes in the linked list.

References

Translate »