How to reverse single linked list?

Node in a single linked list points to the next node by next pointer. Now say we start from head and want to reverse the entire list. This could be possible by reversing the direction of next pointer. To achieve this we require three pointers. One to point previous node another to point the current and one to point to next. Now head will become tail in the reversed list so we take prev pointer as NULL. Current will point to head and next will be Current -> next. Now swap next by pointing next to prev. Move to next node. Prev becomes Current. Current becomes next. and Next is Current ->next. Again point Current->next to Prev. This way shift till next becomes NULL.

Source Code

 #include <stdio.h>

 #include <stdlib.h>

 typedef struct _node {

   int value;

   struct node *next;

 }node;

 int main(int argc, char *argv[])

 {

   int i;

   node *n[10], *head, *tail;

   node *tmp, *tmp_next, *tmp_prev;

   /* Constructing a linked list of 10 nodes */

   for (i = 0; i < 10; i++)

   {

     n[i] = (node *) malloc (sizeof(node));

     n[i]->value = i + 1;

     n[i]->next = NULL;

     if (i > 0) {

       n[i -1]->next = n[i];

     }

   }

   head = n[0];

   tail = n[9];

   tmp = head;

   printf ("Linked List\n");

   while(tmp)

   {

     printf ("Node location %p Value %d\n", tmp, tmp->value);

     tmp = tmp->next;

   }

   tmp = head;

   tmp_prev = NULL;

   while(tmp)

   {

     tmp_next = tmp->next;

     tmp->next = tmp_prev;

     tmp_prev = tmp;

     tmp = tmp_next;

   }

   printf ("Linked List reversed\n");

   printf ("Linked List\n");

   tmp = tail;

   while(tmp)

   {

     printf ("Node location %p Value %d\n", tmp, tmp->value);

     tmp = tmp->next;

   }

   return 0;

 }

Output

Linked List
Node location 005F1880 Value 1
Node location 005F18A0 Value 2
Node location 005F18B0 Value 3
Node location 005F8DB8 Value 4
Node location 005F8DC8 Value 5
Node location 005F8DD8 Value 6
Node location 005F8DE8 Value 7
Node location 005F8DF8 Value 8
Node location 005F8E08 Value 9
Node location 005F8E18 Value 10
Linked List reversed
Linked List
Node location 005F8E18 Value 10
Node location 005F8E08 Value 9
Node location 005F8DF8 Value 8
Node location 005F8DE8 Value 7
Node location 005F8DD8 Value 6
Node location 005F8DC8 Value 5
Node location 005F8DB8 Value 4
Node location 005F18B0 Value 3
Node location 005F18A0 Value 2
Node location 005F1880 Value 1

About our authors: Team EQA

You have viewed 1 page out of 248. Your C learning is 0.00% complete. Login to check your learning progress.

‹ # ›