*666*

Question: How will you reverse a singly Linked List?

Input:– 4 -> 8 -> 15 -> 16 -> 23 -> 42

Output:– 42 -> 23 -> 16 -> 15 -> 8 -> 4

Reversing a singly Linked List is based upon a very simple concept. We just need to swap the “NEXT” value of each of the node, as we iterate over the list.

That means that after the complete process, the first node should point to NULL, and the second last node should point to the first node…and so on.

Initial Condition:-

8 -> NEXT is 15

15 -> NEXT is 16

After “1” iteration

16 -> NEXT is 15

15 -> NEXT is 8

After the entire process is complete, we set the last node as the HEAD and assign NULL to the first node.

Here is an implementation of the same in C.

#include<stdio.h> struct node { int data; struct node * next; }; //function to reverse a single Linked List struct node * reverseList(struct node * head) { // we will use these 2 variables to swap the pointers of next nodes struct node * temp = NULL; struct node * nextNode = NULL; // loop to reverse the list while(head) { // storing the pointer of the next node nextNode = head -> next; // swap started // changing the NEXT pointer of 1st node head -> next = temp; // storing the address to continue the swap in next iteration temp = head; head = nextNode; } // after the loop is complete, temp points at the last node // or we can say, the first node of the reversed list // we return this value. return temp; } void printList(struct node * head) { while(head != NULL) { printf("%d ",head->data); head = head->next; } } struct node * addElement(struct node *head, int number) { struct node * temp = (struct node*)malloc(sizeof(struct node)); temp -> data = number; temp -> next = NULL; struct node * temp2 = head; while(temp2 -> next != NULL) temp2 = temp2 -> next; temp2 -> next = temp; return head; } int main(void) { //creating a list struct node * listHead = (struct node*)malloc(sizeof(struct node)); listHead->data = 4; listHead->next = NULL; listHead = addElement(listHead, 8); listHead = addElement(listHead, 15); listHead = addElement(listHead, 16); listHead = addElement(listHead, 23); listHead = addElement(listHead, 42); printList(listHead); // Initial list listHead = reverseList(listHead); printList(listHead); // Reversed list return 0; }

4, 8, 15, 16, 23, 42

42, 23, 16, 15, 8, 4