The following program generates N random integers between 0 and 999, creates a linked list inserting a number in each node and then rearranges the nodes of the list so that the numbers appear sorted when we go through the list. For the sorting, it maintains two lists: one input list (not sorted) and one output list (sorted). In each iteration of the loop, it removes a node from the input list and enters it in the appropriate position in the output list. The code is simplified by using head nodes for each list, which contains links to the first node lists. Also, both lists (input and output) are printed.

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>
#include <cstdlib>
using namespace std;

struct node {
  int item; node * next;

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

typedef node * plink;

int
main () {
  const int N = 20;

  srand (time (NULL));

  node heada (0, 0); plink a = &heada, t = a;
  for (int i = 0; i < N; i++)
    t = (t->next = new node (rand () % 1000, 0));

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

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

  node headb (0, 0); plink u, x, b = &headb;
  for (t = a->next; t != 0; t = u) {
    u = t->next;

    for (x = b; x->next != 0; x = x->next)
      if (x->next->item > t->item)
        break;

    t->next = x->next; x->next = t;
  }

  cout << "Sorted Sequence:" << endl;

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

  return 0;
}