Reverse Linked List

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:

1. Using Recursion
2. 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

1. Store head.next in a temporary pointer ptr.
2. Call reverseLL(head.next).
3. Store the pointer returned by reverseLL(head.next) in temp.
4. Set ptr.next = head ( ptr points to the last node of the reversed list in temp ).
5. 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

1. Declare 3 nodes: previous, current, and next.
2. Set: previous = null, current = head, next = head.next.
3. Repeat the following steps while next!=null.
   • current.next = previous
   • previous = current
   • current = next
   • next = next.next
4. Set current.next = previous.
5. 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