A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The objective is to reverse a linked list given a pointer to the head node. By altering the connections between the nodes, the list must be reversed.
How to reverse a linked list iteratively
Curr, Prev, and Next are three pointers that are supposed to be used to maintain track of nodes and update reverse linkages.
Algorithm
Initialize three pointers prev as NULL, curr as head, and next as NULL.
Iterate through the linked list. In a loop, do the following:
Before changing the next of curr, store the next node
next = curr -> next
Now update the next pointer of curr to the prev
curr -> next = prev
Update prev as curr and curr as next
prev = curr
curr = next
Example
C program for reversing the linked list.
#include <stdio.h>
#include <stdlib.h>
/* Link list node */
struct Node {
int data;
struct Node* next;
};
/* Function to reverse the linked list */
static void reverse(struct Node** head)
{
struct Node* prev = NULL;
struct Node* current = *head;
struct Node* next = NULL;
while (current != NULL) {
next = current->next;
// Reverse current node's pointer
current->next = prev;
// Move pointers one position ahead.
prev = current;
current = next;
}
*head = prev;
}
/* Function to push a node */
void push(struct Node** head, int new_data)
{
struct Node* new_node
= (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head);
(*head) = new_node;
}
/* Function to print 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, 89); //add elements to linkedlist
push(&head, 3);
push(&head, 45);
push(&head, 23);
printf("Linked list\n");
printList(head);
reverse(&head);
printf("\nReversed linked list \n");
printList(head);
getchar();
}
Output
Linked list 2345389 Reversed linked list 8934523
Time Complexity: O(N), Traversing over the linked list of size N.
Auxiliary Space: O(1)
Reverse a linked list using recursion
The goal is to use recursion to get to the linked list's last node before beginning the reverse operation.
Algorithm
The initial node and the remainder of the linked list should be separated into two parts.
For the rest of the linked list, call reverse.
Add a link to the first in the linked list.
Make the head pointer NULL.
Example:
#include <stdio.h> #include <stdlib.h> /* Link list node */ struct Node { int data; struct Node* next; }; /* Function to reverse the linked list */ static struct Node* reverse(struct Node* head) { if (head == NULL || head->next == NULL) return head; /* reverse the rest list and put the first element at the end */ struct Node* rest = reverse(head->next); head->next->next = head; head->next = NULL; /* fix the head pointer */ return head; } /* Function to push a node */ struct Node * push(struct Node* head, int new_data) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = new_data; new_node->next = head; head = new_node; } /* Function to print 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; head=push(head, 89); //add elements to linkedlist head=push(head, 3); head=push(head, 45); head=push(head, 23); printf("Linked list\n"); printList(head); head=reverse(head); printf("\nReversed linked list \n"); printList(head); getchar(); }
