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.

reverse a single linked list

Source Code

#include <stdio.h>
#include <stdlib.h>
typedef struct _node {
  int value;
  struct node *next;
}node;
int main(int argc, char *argv[])
10  {
11    int i;
12    node *n[10], *head, *tail;
13    node *tmp, *tmp_next, *tmp_prev;
14    /* Constructing a linked list of 10 nodes */
15    for (= 0; i < 10; i++)
16    {
17      n[i] = (node *) malloc (sizeof(node));
18      n[i]->value = i + 1;
19      n[i]->next = NULL;
20      if (> 0) {
21        n[-1]->next = n[i];
22      }
23    }
24    head = n[0];
25    tail = n[9];
26    tmp = head;
27    printf ("Linked List\n");
28    while(tmp)
29    {
30      printf ("Node location %p Value %d\n", tmp, tmp->value);
31      tmp = tmp->next;
32    }
33    tmp = head;
34    tmp_prev = NULL;
35    while(tmp)
36    {
37      tmp_next = tmp->next;
38      tmp->next = tmp_prev;
39      tmp_prev = tmp;
40      tmp = tmp_next;
41    }
42    printf ("Linked List reversed\n");
43    printf ("Linked List\n");
44    tmp = tail;
45    while(tmp)
46    {
47      printf ("Node location %p Value %d\n", tmp, tmp->value);
48      tmp = tmp->next;
49    }
50    return 0;
51  }

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

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

 Vote 0

Similar topics related to this section

Single Linked list, Doubly Linked list, Circular Linked list, Doubly Circular Linked list, Queue, reverse single linked list, delete single linked list, Stack, Tree and Binary tree,

# C Programming Language (Prentice Hall Software)
# Let Us C Paperback - 2006 by Yashavant Kanetkar
# Understanding and Using C Pointers Core techniques for memory management
# Data Structures Using C and C++ Paperback - 1998
# Data Structures In C Paperback - August 11, 2008 by Noel Kalicharan