Tuesday, 27 January 2015

Reversing the Linked List in C/C++ with examples

Reversing the Linked List in C/Cpp with example:

There are two ways to reverse the linked list:

1. We need to know more about the pointers or we have more knowledge on pointers.

2. Swapping starts from the first node’s object and the first node’s object is swapped with the last node’s object. Then, the second node’s object is swapped with the one before the last node’s object.

For example we have we have N nodes in the link list:
Swap: 1st node’s object with Nth node’s object
Swap: 2nd node’s object with (N-1)th node’s object
Swap: 3rd node’s object with (N-2)th node’s object
Swap: 4th node’s object with (N-3)th node’s object

Let see the pictorial representation of the above technique

3. The third way is that the head of the linked list will point to the last node of the linked list. Also, each node’s “Next” and “Previous” properties need to be swapped too.Next and Previous (blue arrow) are swapped

Let us see the sample code that is used to reverse the linked list using swaping method (method -2 )
#include <stdio.h>
#include <stdlib.h>
#define SIZE 25    /* SIZE of 10 elements */
struct StNode {
 int INodeNo;
 struct StNode *PstNext;
};

/* add a StNode at the beginning of the list */
void AddList(struct StNode **n, int val);

/* reverse the whole list */
void Reverse(struct StNode **n);

/* display the whole linked list */
void ShowList(struct StNode *n);
void AddList(struct StNode **n, int val)  {
 struct StNode *NodeTemp = NULL;

 /* add new node */
 NodeTemp = malloc(sizeof(struct StNode));
 NodeTemp->INodeNo = val;
 NodeTemp->PstNext = *n;
 *n = NodeTemp;
}

/* reverse the whole list */
void Reverse(struct StNode **n)  {
 struct StNode *a = NULL;
 struct StNode *b = NULL;
 struct StNode *c = NULL;
 a = *n, b = NULL;
 while(a != NULL) {
  c = b, b = a, a = a->PstNext;
  b->NodeNext = c;
 }
 *n = b;
}

/* display the whole linked list */
void ShowList(struct StNode *n) {
 while(n != NULL)
  printf(" %d", n->NodeNumber), n = n->NodeNext;
 printf("\n");
}
int main(void) {
 struct StNode *new = NULL;
 int i = 0;

 /* insert some INodeNos */
 for(i = 0; i <= SIZE; i++)
  AddList(&new, i);
 ShowList(new);
 Reverse(&new);
 ShowList(new);
 return 0;
}

No comments: