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.

#### 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 *prev = NULL, *next = NULL;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
}
void print()
{
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);
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)
{
System.out.println("");
}
}
```
```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()
{
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);
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;
}
}
}
public void insertNode(int nodeData) {
Node node = new Node(nodeData);
}
}
}
String sep) throws IOException {
while (node != null) {
System.out.print(String.valueOf(node.data) + sep);
node = node.next;
}
}
}
}
}
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();
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;
}
{
cout << head->data << " ";
}
cout << endl;
}
int main()
{
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)
{
System.out.println("");
System.out.println("");
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 »