# Program to Reverse a Linked List using Loop and Recursion

• Write a C program to reverse a linked list using loop and recursion.

Given a singly linked list having N nodes, we have to reverse the sequence of nodes of given linked list. Here we will a linked list using both iterative and recursive approach.

```Input Linked List
1 -- > 3 --> 9 --> 12 --> 5 --> NULL
5 --> 12 --> 9 --> 3 --> 1 --> NULL
```

## Reverse a Linked List using Iteration

Algorithm to reverse a linked list using iteration
We will use three node pointer "previous", "current" and "next" to keep track of previous, current and next node during linked list reversal.
• Initialize current pointer to head and previous pointer to NULL.
• In every iteration, set current->next = previous; and move all three pointers to next node.
• Return previous pointer. This is the new head pointer of reversed linked list.

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

/* A structure of linked list node */
struct node {
int data;
struct node *next;

void initialize(){
}

/*
Given a Inserts a node in front of a singly linked list.
*/
void insert(int num) {
/* Create a new Linked List node */
struct node* newNode = (struct node*) malloc(sizeof(struct node));
newNode->data  = num;
/* Next pointer of new node will point to head node of linked list  */
printf("Inserted Element : %d\n", num);
}

/* Reverses a given Linked List, and return
struct node *previous, *current, *next;
previous = NULL;

while (current != NULL) {
next  = current->next;
current->next = previous;
previous = current;
current = next;
}
return previous;
}

/*
*/
while (nodePtr != NULL) {
printf("%d", nodePtr->data);
nodePtr = nodePtr->next;
if(nodePtr != NULL)
printf("-->");
}
}

int main() {
initialize();
insert(8);
insert(3);
insert(2);
insert(7);
insert(9);

return 0;
}
```
Output
```Inserted Element : 8
Inserted Element : 3
Inserted Element : 2
Inserted Element : 7
Inserted Element : 9

8-->3-->2-->7-->9
9-->7-->2-->3-->8
```

## Reverse a Linked List using Recursion

Algorithm to reverse a linked list using iteration
Let "reverse(struct node* nodePtr)" be the recursive function which reverses a linked list whose head node is pointed by nodePtr.
• Recursion termination condition : if(nodePtr->next == NULL) set head = nodePtr;
• Recursively call "reverse" function to reverse sub list reverse(nodePtr->next);
• Add nodePtr to the end of the reversed Llinked List. Set nodePtr->next->next = nodePtr;
• Now, nodePtr is the tail node of reversed linked list. Set nodePtr->next = NULL.

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

/* A structure of linked list node */
struct node {
int data;
struct node *next;

void initialize(){
}

/*
Given a Inserts a node in front of a singly linked list.
*/
void insert(int num) {
/* Create a new Linked List node */
struct node* newNode = (struct node*) malloc(sizeof(struct node));
newNode->data  = num;
/* Next pointer of new node will point to head node of linked list  */
printf("Inserted Element : %d\n", num);
}

/* Reverses a Linked List using recursion */
void reverse(struct node* nodePtr) {

/* empty list */
if (nodePtr == NULL)
return;
/* Last node (tail node)*/
if(nodePtr->next == NULL){
return;
}

/* reverse the rest of list and put the first element at the end */
reverse(nodePtr->next);
nodePtr->next->next = nodePtr;
nodePtr->next = NULL;
}

/*
*/
while (nodePtr != NULL) {
printf("%d", nodePtr->data);
nodePtr = nodePtr->next;
if(nodePtr != NULL)
printf("-->");
}
}

int main() {
initialize();
insert(1);
insert(2);
insert(3);
insert(4);
insert(5);

return 0;
}
```
Output
```Inserted Element : 1
Inserted Element : 2
Inserted Element : 3
Inserted Element : 4
Inserted Element : 5