- 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 Reversed Linked List 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.
- Traverse linked list from head till current->next != 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; } *head; void initialize(){ head = NULL; } /* 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 */ newNode->next = head; /* make new node as new head of linked list */ head = newNode; printf("Inserted Element : %d\n", num); } /* Reverses a given Linked List, and return the head pointer of reversed linked list */ struct node* reverseLinkedList(struct node *head) { struct node *previous, *current, *next; previous = NULL; current = head; while (current != NULL) { next = current->next; current->next = previous; previous = current; current = next; } return previous; } /* Prints a linked list from head node till tail node */ void printLinkedList(struct node *nodePtr) { while (nodePtr != NULL) { printf("%d", nodePtr->data); nodePtr = nodePtr->next; if(nodePtr != NULL) printf("-->"); } } int main() { initialize(); /* Creating a linked List*/ insert(8); insert(3); insert(2); insert(7); insert(9); printf("\nLinked List\n"); printLinkedList(head); /* Reverse Linked List */ head = reverseLinkedList(head); printf("\nReversed Linked List\n"); printLinkedList(head); return 0; }Output

Inserted Element : 8 Inserted Element : 3 Inserted Element : 2 Inserted Element : 7 Inserted Element : 9 Linked List 8-->3-->2-->7-->9 Reversed Linked List 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; } *head; void initialize(){ head = NULL; } /* 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 */ newNode->next = head; /* make new node as new head of linked list */ head = newNode; 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){ head = nodePtr; return; } /* reverse the rest of list and put the first element at the end */ reverse(nodePtr->next); nodePtr->next->next = nodePtr; nodePtr->next = NULL; } /* Prints a linked list from head node till tail node */ void printLinkedList(struct node *nodePtr) { while (nodePtr != NULL) { printf("%d", nodePtr->data); nodePtr = nodePtr->next; if(nodePtr != NULL) printf("-->"); } } int main() { initialize(); /* Creating a linked List*/ insert(1); insert(2); insert(3); insert(4); insert(5); printf("\nLinked List\n"); printLinkedList(head); /* Reverse Linked List */ reverse(head); printf("\nReversed Linked List\n"); printLinkedList(head); return 0; }Output

Inserted Element : 1 Inserted Element : 2 Inserted Element : 3 Inserted Element : 4 Inserted Element : 5 Linked List 5-->4-->3-->2-->1 Reversed Linked List 1-->2-->3-->4-->5