In this article, we will be studying how to reverse Linked List using recursion and without recursion.
Each element/node of a Linked List store the address of the next node. To reverse the list, each node should store the address of the previous node.
Example,

We can reverse Linked List in two ways:
- Using Recursion
- Using Iteration
Reverse Linked List using Recursion
Let reverseLL() be the function that accepts Linked List head as an argument and returns the reversed Linked List.
On each recursive call, we remove the first node from the list and pass the rest of the list to reverseLL(). reverseLL() then returns the head of the reversed LinkedList. We add the node we removed in the beginning, at the end of the returned list.
Following illustration shows how a recursive call works,

Steps
- Store head.next in a temporary pointer ptr.
- Call reverseLL(head.next).
- Store the pointer returned by reverseLL(head.next) in temp.
- Set ptr.next = head ( ptr points to the last node of the reversed list in temp ).
- temp points to the first node of the reversed list.
Pseudo Code
FUNC reverseLL ( node head ) IF head.next == NULL THEN RETURN head END IF node ptr := head.next // temp stores the reversed List returned by reverseLL // head.node,ptr becomes the last node of the linked list node temp := reverseLL(head.next) // the following 2 lines // inserts head at the end of the // returned linked list head.next := NULL ptr.next = head END FUNC
Program
#include<stdio.h> #include<stdlib.h> struct node{ int v; struct node *next; }; // head points to the first node of the linkedlist struct node *head; // inserts value at the front of LinkedList head void insertAtBegin(int value){ struct node *temp = (struct node*)malloc(sizeof(struct node)); temp->v = value; if(head==NULL){ temp->next = NULL; head = temp; return; } temp->next = head; head = temp; } // display linkedlist void displayLL(struct node* head){ struct node *temp = head; while(temp!=NULL){ printf("%d->",temp->v); temp = temp->next; } printf("NULL \n\n"); } // reverse linkedlist struct node* reverseLL(struct node* head){ if(head==NULL||head->next==NULL){ return head; } struct node *ptr = head->next; struct node *temp = reverseLL(head->next); head->next = NULL; ptr->next = head; return temp; } int main(){ insertAtBegin(3); insertAtBegin(5); insertAtBegin(10); insertAtBegin(15); insertAtBegin(20); printf("LinkedList:\n"); displayLL(head); head = reverseLL(head); printf("LinkedList after Reverse:\n"); displayLL(head); }
Output
LinkedList: 20->15->10->5->3->NULL LinkedList after Reverse: 3->5->10->15->20->NULL
Reverse Linked List without Recursion
In this method, we use 3 pointers. We keep reversing the direction of the pointer of every node iteratively.
Pointers:
previous: Stores address of the previous node
current: Stores address of the current node
next: Stores address of next node
Following diagram illustrates how it works,

Steps
- Declare 3 nodes: previous, current, and next.
- Set: previous = null, current = head, next = head.next.
- Repeat the following steps while next!=null.
- current.next = previous
- previous = current
- current = next
- next = next.next
- Set current.next = previous.
- current points to the first node of reversed list.
Pseudo Code
FUNC reverseLL( node head ) IF head == NULL THEN RETURN head END IF previous := NULL current := head next := head.next WHILE next != NULL DO current.next = previous previous = current current = next next = next.next END WHILE current.next = previous RETURN current END FUNC
Program
#include<stdio.h> #include<stdlib.h> struct node{ int v; struct node *next; }; // head points to the first node of the linkedlist struct node *head; // inserts value at the front of LinkedList head void insertAtBegin(int value){ struct node *temp = (struct node*)malloc(sizeof(struct node)); temp->v = value; if(head==NULL){ temp->next = NULL; head = temp; return; } temp->next = head; head = temp; } // display linkedlist void displayLL(struct node* head){ struct node *temp = head; while(temp!=NULL){ printf("%d->",temp->v); temp = temp->next; } printf("NULL \n\n"); } // reverse linkedlist struct node* reverseLL(struct node* head){ if(head==NULL) return head; struct node *previous, *current, *next; previous = NULL; current = head; next = head->next; while(next!=NULL){ current->next = previous; previous = current; current = next; next = next->next; } current->next = previous; return current; } int main(){ insertAtBegin(3); insertAtBegin(5); insertAtBegin(10); insertAtBegin(15); insertAtBegin(20); printf("LinkedList:\n"); displayLL(head); head = reverseLL(head); printf("LinkedList after Reverse:\n"); displayLL(head); }
Output
LinkedList: 20->15->10->5->3->NULL LinkedList after Reverse: 3->5->10->15->20->NULL
Note: The above Program can also be implemented using 2 pointers instead of 3. We just have to replace current with head.
References
https://en.wikipedia.org/wiki/Linked_list