Last Updated on December 14, 2022 by Prepbytes

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.

**Other C Programs**

C program to calculate percentage of 5 subjects

C program to convert binary number to decimal number

C program to convert celsius to fahrenheit

C program to convert infix to postfix

C program to find area of circle

C program to find roots of quadratic equation

C program to reverse a number

C program for merge sort for linked lists

C program for performing bubble sort on linked list

C program to add two numbers