### Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

### Problem Statement

In this problem, we will be given a singly linked list, and we will have to reverse it.

Check out the sample input-output below.

##### Sample Input

##### Sample Output

**Explanation:** The input list has been reversed.

### Problem Statement Understanding

Letâ€™s try to understand the problem with the help of a example.

Suppose the given linked list is:

To reverse the given linked list, we will have to change the links of all the nodes of the linked list such that:

- 1â†’7 will become 7â†’1.
- 7â†’15 becomes 15â†’7.
- 15â†’27 becomes 27â†’15.

Finally, after changing the links, we will have to make 27 as the new head of the linked list. So, the final reverse linked list will be:

Now, I think from the above example, the reversal of the linked list is clear. Letâ€™s see how we can approach it.

Before moving to the approach section, try to think about how you can approach this problem.

- If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.

Letâ€™s move to the approach section.

### Approach and Algorithm (Iterative method)

The approach is going to be pretty straightforward:

- First, we will create three-pointers, say,
**prev**,**current**and**next**. - Initailly
**prev**and**next**will point to**NULL**and the**current**will point to the**head**of the list. - Now, we will traverse the list until the
**current**is not NULL.- For every
**current**node during list traversal, we will store the**next of current**in**next**and then make the**next of current**point to**prev**. - After that, we will make
**prev**equal to**current**and**current**equal to**next**.

- For every
- At last, after the traversal is over, we will make the node to which
**prev**is pointing our**new linked list head**. - By performing the above operations, we are changing the links of every node and ultimately reversing the list.

#### Dry Run

#### Code Implementation:

#include <stdio.h> #include <stdlib.h> /* Node structure of a singly linked list node */ struct Node { int data; struct Node* next; }; /* Using this function we will reverse the given linked list */ static void reverse(struct Node** head_ref) { struct Node* prev = NULL; struct Node* current = *head_ref; struct Node* next = NULL; while (current != NULL) { next = current->next; current->next = prev; prev = current; current = next; } *head_ref = prev; } /* Using this function we are inserting a new node at head of the linked list */ void push(struct Node** head_ref, int new_data) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } /* Using this function we will print the content of linked list */ void printList(struct Node* head) { struct Node* temp = head; while (temp != NULL) { printf("%d ", temp->data); temp = temp->next; } } int main() { struct Node* head = NULL; push(&head, 21); push(&head, 15); push(&head, 71); push(&head, 1); printf("\nOriginal Linked list: \n"); printList(head); reverse(&head); printf("\nReversed Linked list: \n"); printList(head); getchar(); }

#### Output

Original Linked list:

1 71 15 21

Reversed Linked list:

21 15 71 1

**Time Complexity** O(n), where n is the total number of nodes in the Singly Linked List.

**Space complexity** O(1), a constant amount of additional space used.

### Approach and Algorithm(Recursive Method)

Here, we will see how we can reverse the linked list using recursion.

**Base Case:**Inside the recursive function, if the head is NULL, we return.- Otherwise, We need to create two pointers,
**first**and**rest**:**first**points the**head node**.**rest**points to**first->next**.

- Then we need to check if the
**rest**is NULL:- If yes, we assign the pointer
**first**to**head**and return from the function. - Else, move to the next step.

- If yes, we assign the pointer
- If there are more than 1 node, i.e. not the base case, we will recursively call the function with
**rest**as the**new head**and**original head reference**. - While returning from the recursive call, we will assign the
**next of rest node**as**first**and the**next of the first node**as NULL. - At the time when our recursion is over, our linked list will be reversed.

#### Dry Run(recursive method)

![](https://blog.prepbytes.com/wp-content/uploads/2021/10/p_5-3.png)

![](https://blog.prepbytes.com/wp-content/uploads/2021/10/p_6-2.png)

#### Code implementation

#include <stdio.h> #include <stdlib.h> /* Node structure of a linked list node */ struct Node { int data; struct Node* next; }; /* Using this function we will print the content of linked list */ void printList(struct Node* head) { struct Node* ptr = head; while (ptr) { printf("%d ", ptr->data); ptr = ptr->next; } } /* Using this function we are inserting a new node at head of the linked list */ void push(struct Node** head, int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; newNode->next = *head; *head = newNode; } /* Using this function we will reverse the given linked list */ void recursiveReverse(struct Node* head, struct Node** headRef) { struct Node* first; struct Node* rest; if (head == NULL) { return; } first = head; rest = first->next; if (rest == NULL) { *headRef = first; return; } recursiveReverse(rest, headRef); rest->next = first; first->next = NULL; } void reverse(struct Node** head) { recursiveReverse(*head, head); } int main() { struct Node* head = NULL; push(&head, 21); push(&head, 15); push(&head, 71); push(&head, 1); printf("\nOriginal Linked list: \n"); printList(head); reverse(&head); printf("\nReversed Linked list: \n"); printList(head); return 0; }

#### Output

Original Linked list:

1 71 15 21

Reversed Linked list:

21 15 71 1

**Time Complexity** O(n), where n is the total number of nodes in the Singly Linked List.

[forminator_quiz id=”5440″]

So, in this blog, we have tried to explain how to reverse a linked list. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.