# How to Reverse a Linked List? (C and Python Implementation)

Filed Under: C Programming

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. 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.

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:
1. Previous node = current node
2. Current node = next node
3. 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;

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);
}

void print_list(){
while(cur){
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}

void reverse_list(){
return;
struct node *prev = NULL, *cur = head, *next;
while(cur){
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
}

int main(){

push(3);
push(4);
push(5);
push(6);

print_list();

reverse_list();

print_list();

return 0;
}
``````

### Code in Python

``````
class Node:

def __init__(self, data):
self.data = data
self.next = None

def __init__(self):

def reverse(self):
return

prev = None

while cur:
next_element = cur.next
cur.next = prev
prev = cur
cur = next_element

def push(self, data):
new_node = Node(data)

def print_list(self):
l1 = []
while cur:
l1.append(cur.data)
cur = cur.next
return l1

``````

## 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:
2. 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;

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);
}

void print_list(){
while(cur){
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}

struct node *reverse_list(struct node *prev, struct node *cur){
if(cur == NULL){
}
else{
reverse_list(cur, cur->next);
cur->next = prev;
}
}

int main(){

push(3);
push(4);
push(5);
push(6);

print_list();

print_list();

return 0;
}
``````

### Code in Python

``````
class Node:

def __init__(self, data):
self.data = data
self.next = None

def __init__(self):

def _reverse(self, prev, cur):

if cur is None:

else:
self._reverse(cur, cur.next)
cur.next = prev

def reverse(self):

def push(self, data):

new_node = Node(data)

def print_list(self):

l1 = []
while cur:
l1.append(cur.data)
cur = cur.next
return l1

``````

Output Reverse Linked List using Recursion – Python

1. chirag shetty says:

class Node:
def __init__(self,data):
self.data = data
self.ref = None

def __init__(self):

def printLL(self):
print(“list is empty”)

else:
while n is not None:
print(n.data)
n=n.ref

new_node = Node(data)

else:
while n.ref is not None:
n=n.ref
n.ref = new_node

def reverseList(self):
prev = None
while n:
temp = n
temp.ref = prev
prev = temp