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