Winter Bootcamp in ML and IoT in Jaipur
 Course content (For Bootcamp & Winter Training):- Machine Learning (ML) || Internet of Things (IoT) || Register for winter bootcamp
0 like 0 dislike
in Tutorial & Interview questions by (3.3k points)

Reversing a linked list

1 Answer

0 like 0 dislike
by (3.3k points)
 
Best answer

You can also perform this task recursively, but I have chosen in this example to use an iterative approach. This task is useful if you are inserting all of your nodes at the beginning of a linked list. Here is an example:

#include <stdio.h> 

#include <stdlib.h>

#define NUM_ITEMS 10

struct Node 

{  

int data;  

struct Node *next; 

};

void insert_node(struct Node **headNode, int nodeValue, int position); 

void print_list(struct Node *headNode);

void reverse_list(struct Node **headNode);

int main(void) 

{  

int i;  

struct Node *head = NULL;

for(i = 1; i <= NUM_ITEMS; i++) 

{    

insert_node(&head, i, i);  

}  

print_list(head);

printf("I will now reverse the linked list\n");  

reverse_list(&head);  

print_list(head);  

return 0; 

}

void print_list(struct Node *headNode) 

{  

struct Node *iterator;

for(iterator = headNode; 

iterator != NULL; 

iterator = iterator->next) 

{    

printf("Value: %d\n", iterator->data);  

}

void insert_node(struct Node **headNode, int nodeValue, int position) 

{  

int i;  

struct Node *currentNode = (struct Node *)malloc(sizeof(struct Node));  

struct Node *nodeBeforePosition = *headNode;

currentNode->data = nodeValue;

if(position == 1) 

{    

currentNode->next = *headNode;    

*headNode = currentNode;    

return;  

}

for (i = 0; i < position - 2; i++) 

{    

nodeBeforePosition = nodeBeforePosition->next;  

}

currentNode->next = nodeBeforePosition->next;  

nodeBeforePosition->next = currentNode; 

}

void reverse_list(struct Node **headNode) 

{  

struct Node *iterator = *headNode;  

struct Node *previousNode = NULL;  

struct Node *nextNode = NULL;

while (iterator != NULL) 

{    

nextNode = iterator->next;    

iterator->next = previousNode;    

previousNode = iterator;    

iterator = nextNode;  

}

  /* Iterator will be NULL by the end, so the last node will be stored in  previousNode.  We will set the last node to be the headNode */  

*headNode = previousNode;

}

Explanation for the Reverse List Method

We start the previousNode out as NULL, since we know on the first iteration of the loop, if we are looking for the node before the first head node, it will be NULL. The first node will become the last node in the list, and the next variable should naturally be NULL.

Basically, the concept of reversing the linked list here is that we actually reverse the links themselves. Each node's next member will become the node before it, like so:

Head -> 1 -> 2 -> 3 -> 4 -> 5

Where each number represents a node. This list would become:

1 <- 2 <- 3 <- 4 <- 5 <- Head

Finally, the head should point to the 5th node instead, and each node should point to the node previous of it.

Node 1 should point to NULL since there was nothing before it. Node 2 should point to node 1, node 3 should point to node 2, et cetera.

However, there is one small problem with this method. If we break the link to the next node and change it to the previous node, we will not be able to traverse to the next node in the list since the link to it is gone.

The solution to this problem is to simply store the next element in a variable (nextNode) before changing the link. 

Winter 10 Days boot-camp classes(7 HRS Daily) will start from 5, 20 & 27 December 2019 in:
1) Internet of things(IoT) Using RASPBERRY-PI
2) Machine Learning (ML)

70% OFF| Fee-INR 3,000/-

Limited seats!! Hurry up!!

[[ CALL - 07976731765 ]]

Some Study Resources are compiled from original Stack Overflow Documentation, the content is developed by the different experts at Stack Overflow. Study resources are released under Creative Commons BY-SA. Images may be copyright of their respective owners. This website is for self-learning and not affiliated with Stack Overflow. All trademarks and registered trademarks are the property of their respective company owners. Please send feedback and corrections to chandwaglobal@gmail.com.

Goeduhub Important Lists Our Youtube Channels (For free E-learning)
About Us List of IITs Goeduhub Technologies
Contact Us List of NITs AI and Big Data-HADOOP E-Learning Series
  List of PSUs Smart Learning PLC-SCADA, IoT and Raspberry-PI
  List of Exams After Graduation  
...