Home > Articles, Data Structures & Algorithms > Implement simple reverse list iteratively.

Implement simple reverse list iteratively.

The function ‘reverse’ in the following example reverses the links in a list, returning a pointer to the end node, which then shows the next of the last node, and so forth, while the link to the first node of the initial list is assigned the value 0 corresponding to null pointer (in C++). To accomplish this task, we must maintain links to three consecutive nodes in the list.

You should know that the implementation of the algorithm does not take into account issues of data input validation or proper management of dynamic memory (e.g. avoiding memory leaks) because it is only necessary to highlight the logic of the algorithm.

#include <iostream>
#include <iomanip>
using namespace std;

struct node {
  int item; node * next;

  node (int x, node * t) {
    item = x; next = t;
  }
};

typedef node * plink;

plink
reverse (plink x) {
  plink t, y = x, r = 0;

  while (y != 0) {
    t = y->next; y->next = r;

    r = y; y = t;
  }

  return r;
}

int
main () {
  const int N = 20;

  plink c, head = new node (1, 0);

  c = head;
  for (int i = 2; i <= N; i++)
    c = c->next = new node (i, 0);

  cout << "Initial Sequence: " << endl;

  c = head;
  while (c != 0) {
    cout << setw (5) << c->item << right << endl;
    c = c->next;
  }

  cout << "Reversed Sequence: " << endl;

  c = reverse (head);
  while (c != 0) {
    cout << setw (5) << c->item << right << endl;
    c = c->next;
  }

  return 0;
}
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: