# 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, reverse linked list without recursion

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