Write a C program to reverse a linked list in place, without using any extra memory.

Question

Aryan Kumar · Answer

#include andlt;stdio.h>
#include andlt;stdlib.h>
// Define the linked list node
struct ListNode {
   int val;
   struct ListNode* next;
};
// Function to create a new linked list node
struct ListNode* newNode(int data) {
   struct ListNode* node = (struct ListNode*) malloc(sizeof(struct ListNode));
   node->val = data;
   node->next = NULL;
   return node;
}
// Function to reverse a linked list in place
struct ListNode* reverseList(struct ListNode* head) {
   struct ListNode *prev = NULL, *curr = head, *next = NULL;
   while (curr != NULL) {
       next = curr->next;
       curr->next = prev;
       prev = curr;
       curr = next;
   }
   return prev;
}
int main() {
   struct ListNode* head = newNode(1);
   head->next = newNode(2);
   head->next->next = newNode(3);
   head->next->next->next = newNode(4);
   head->next->next->next->next = newNode(5);
   printf("Original List: ");
   struct ListNode* node = head;
   while (node != NULL) {
       printf("%d ", node->val);
       node = node->next;
   }
   printf("
");
   head = reverseList(head);
   printf("Reversed List: ");
   node = head;
   while (node != NULL) {
       printf("%d ", node->val);
       node = node->next;
   }
   printf("
");
   return 0;
}
In this program, we define the linked list node structure and a function to create a new linked list node. We then define a function
reverseList that takes the head of a linked list as an argument and returns a pointer to the head of the reversed linked list. The function uses three pointers,
prev, curr, and next, to keep track of the previous, current, and next nodes in the original linked list. Initially,
prev is NULL, curr is the head of the linked list, and
next is NULL. We traverse the linked list using a while loop and for each node, we set
next to the next node, set the curr->next pointer to
prev, set prev to curr, and set
curr to next. Finally, we return prev, which is the head of the reversed linked list.
In the main function, we create a linked list and print the original list. We then call the
reverseList function to reverse the linked list in place and print the reversed list.

forum

Write a C program to reverse a linked list in place, without using any extra memory.

Utpal Vishwas

Can you answer this question?

1 Answers

Liked By