How to Reverse a Linked List? (C and Python Implementation) With Examples [Latest]

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.

Java LinkedList – LinkedList In Java

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:
  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;
} *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:
  1. We would first move ahead in the linked list.
  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;
} *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