Friday, January 24, 2020

Posted on Leave a Comment

Reverse of a linked list

Program to create a singly linked list, reverse it and display both the list.

Reverse of a linked list source code


#include 

// The list element type and head.

struct node {
  int data;
  struct node * link;
};
static struct node * first = NULL;

// A reverse function which uses only two extra pointers.

void reverse() {
  struct node * nxtNode, * curNode;

  // curNode traverses the list, first is reset to empty list.

  curNode = first;
  first = NULL;

  // Until no more in list, insert current before first and advance.

  while (curNode != NULL) {
    // Need to save next node since we’re changing the current.

    nxtNode = curNode - > link;

    // Insert at start of new list.

    curNode - > link = first;
    first = curNode;

    // Advance to next.

    curNode = nxtNode;
  }
}

// Code to dump the current list.

static void dumpNodes() {
  struct node * curNode = first;
  printf(“ === === === = \n”);
  while (curNode != NULL) {
    printf(“ % d\ n”, curNode - > data);
    curNode = curNode - > link;
  }
}

// Test harness main program.

void main() {
  int i, num, n;
  struct node * newnode;
  clrscr();
  // Create list (using actually the same insert-before-first
  // that is used in reverse function.
  printf(“\nEnter total number of nodes: \n”);
  scanf(“ % d”, & n);
  for (i = 0; i < n; i++) {
    newnode = (struct node * ) malloc(sizeof(struct node));
    printf(“\nenter data
      for % d node”, i + 1);
    scanf(“ % d”, & num);
    newnode - > data = num;
    newnode - > link = first;
    first = newnode;
  }

  // Dump list, reverse it, then dump again.
  printf(“\noriginal list is: \n”);
  dumpNodes();
  reverse();
  printf(“\nreversed list is: \n”);
  dumpNodes();
  getch();
}

Output


Enter total number of nodes :
4

enter data for 1 node4

enter data for 2 node9

enter data for 3 node3

enter data for 4 node2

original list is :
==========
2
3
9
4

reversed list is :
==========
4
9
3
2

0 comments:

Post a Comment

Codearea.in is featured by projectsgeek.com. Powered by Blogger.