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

END IF

// temp stores the reversed List returned by reverseLL

// the following 2 lines
// inserts head at the end of the

END FUNC```

### Program

```#include<stdio.h>
#include<stdlib.h>

struct node{
int v;
struct node *next;
};

void insertAtBegin(int value){
struct node *temp = (struct node*)malloc(sizeof(struct node));
temp->v = value;
temp->next = NULL;
return;
}
}

while(temp!=NULL){
printf("%d->",temp->v);
temp = temp->next;
}
printf("NULL \n\n");
}

}
return temp;
}

int main(){

insertAtBegin(3);
insertAtBegin(5);
insertAtBegin(10);
insertAtBegin(15);
insertAtBegin(20);

}```

#### Output

```LinkedList:
20->15->10->5->3->NULL
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.
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 )

END IF

previous := NULL

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

void insertAtBegin(int value){
struct node *temp = (struct node*)malloc(sizeof(struct node));
temp->v = value;
temp->next = NULL;
return;
}
}

while(temp!=NULL){
printf("%d->",temp->v);
temp = temp->next;
}
printf("NULL \n\n");
}

struct node *previous, *current, *next;

previous = NULL;

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

}```

#### Output

```LinkedList:
20->15->10->5->3->NULL