A Linked List is a simple but fascinating data structure that can be used to store linearly connected non-contiguous data.

We are often encountered with interesting manipulative problems using a linked list as they require out-of-the-box thinking with the limited properties of the Singly Linked List.

In this article, we will be discussing the problem to **Reverse a Singly Linked List**.

Throughout the article, I will be assuming that you are able to comprehend basic terminology related to Linked lists. If that is not the case, please refer to the following article(s) before reading on.

Table of Contents

## Reversing a Linked List

Let us dive right into the discussion for the solution. We will discuss two methods:

- Iterative Solution (using 3 pointers)
- Recursive Solution (using pseudo-2 pointers)

**Note**: I would suggest you to try to solve the problem, and then go to the solution.

## Reverse a Linked List using Iterative Solution

- Let us get over with the base cases first. If the linked list has 0 or only 1 node, then it does not make sense to reverse the list, so we can simply return then and there.
- Assuming we have >=2 nodes now, we can do the following.
- Keep 3 pointers on previous node, current node, next node.
- Initially, assign the previous node as NULL, current node as the head and next node as the successor of the head.
- Reverse the link between the previous and current node.
- Move all the pointers one step forward by doing the following:
- Previous node = current node
- Current node = next node
- Next node = next node -> next

- Go to step 5 until the current node does not become NULL.
- Assign head as the previous node and return.

The code following this paradigm can be found here.

### Code in C

```
#include<stdio.h>
#include<stdlib.h>
struct node{
int data;
struct node *next;
} *head = NULL;
struct node *make_node(int data){
struct node *new = (struct node *)malloc(sizeof(struct node));
new->next = NULL; new->data = data;
return new;
}
void push(int data){
struct node *new_node = make_node(data);
new_node->next = head;
head = new_node;
}
void print_list(){
struct node *cur = head;
while(cur){
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
void reverse_list(){
if(head == NULL || head->next == NULL)
return;
struct node *prev = NULL, *cur = head, *next;
while(cur){
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
head = prev;
}
int main(){
push(3);
push(4);
push(5);
push(6);
printf("Given Linked list is: ");
print_list();
reverse_list();
printf("Reversed Linked list is: ");
print_list();
return 0;
}
```

### Code in Python

```
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def reverse(self):
if self.head is None or self.head.next is None:
return
prev = None
cur = self.head
while cur:
next_element = cur.next
cur.next = prev
prev = cur
cur = next_element
self.head = prev
def push(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def print_list(self):
cur = self.head
l1 = []
while cur:
l1.append(cur.data)
cur = cur.next
return l1
head = LinkedList()
head.push(3)
head.push(4)
head.push(5)
head.push(6)
print("Given list is: ", head.print_list())
head.reverse()
print("Reversed list is: ", head.print_list())
```

## Reverse a Linked List using Recursive Solution

The recursive solution is slightly easy to understand as it uses a more natural and easy-to-understand algorithm. Nevertheless, iterative and recursive solutions are similar in working.

We mainly use recursion to replace the pointer ‘next’ as we can recurse forward to the end of the linked list and follow in a similar way as the iterative solution.

The only differences being that we move backward as well after going to the end of the list, due to the use of recursion.

Also, note that in the recursive solution we don’t require a next pointer as recursion allows us to move ahead in the linked list.

Here we define the recursive solution in 2 parts:

- Recursive Case:
- We would first move ahead in the linked list.
- When the recursion ends, we can simply link the current node to the previous node.

- Base Case: If the current element is NULL, then we can simply assign the head as previous node i.e. the last node of the linked list in this case.

The code following this paradigm can be found here:

### Code in C

```
#include<stdio.h>
#include<stdlib.h>
struct node{
int data;
struct node *next;
} *head = NULL;
struct node *make_node(int data){
struct node *new = (struct node *)malloc(sizeof(struct node));
new->next = NULL; new->data = data;
return new;
}
void push(int data){
struct node *new_node = make_node(data);
new_node->next = head;
head = new_node;
}
void print_list(){
struct node *cur = head;
while(cur){
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
struct node *reverse_list(struct node *prev, struct node *cur){
if(cur == NULL){
head = prev;
}
else{
reverse_list(cur, cur->next);
cur->next = prev;
}
}
int main(){
push(3);
push(4);
push(5);
push(6);
printf("Given Linked list is: ");
print_list();
reverse_list(NULL, head);
printf("Reversed Linked list is: ");
print_list();
return 0;
}
```

### Code in Python

```
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def _reverse(self, prev, cur):
if cur is None:
self.head = prev
else:
self._reverse(cur, cur.next)
cur.next = prev
def reverse(self):
self._reverse(None, self.head)
def push(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def print_list(self):
cur = self.head
l1 = []
while cur:
l1.append(cur.data)
cur = cur.next
return l1
head = LinkedList()
head.push(3)
head.push(4)
head.push(5)
head.push(6)
print("Given list is: ", head.print_list())
head.reverse()
print("Reversed list is: ", head.print_list())
```

**Output**