Random list generation program (with comments :)

gistfile1.cpp

#include <iostream>
using namespace std;

struct list_item
{
  list_item *next;
  list_item *rand;
};

void deep_copy(list_item* src, list_item* &dst)
{
  // interleave src with dst such that src_1-->dst_1-->src_2-->dst_2 etc.
  list_item *current = src, *temp;
  dst = NULL;
  while (current != NULL)
  {
    // allocate a matching dst element
    list_item* li = new list_item;
    // if it's the first ever, assign it as the output
    if (dst == NULL)
      dst = li;
    // assign the element's next, but null the rand for now
    li->next = current->next;
    li->rand = NULL;
    // rearrange the pointers for src_n->dst_n and move on
    current->next = li;
    current = li->next;
  }
  // for a given src element, its rand->next is the projected dst element
  for (current = src; current != NULL; current = current->next->next)
  {
    // guard against the (unlikely) case of the rand not pointing anywhere :)
    if (current->rand != NULL)
      current->next->rand = current->rand->next;
  }
  // now separate the src|dst list into two lists
  for (current = src; current != NULL;)
  {
    // cache the next item's address (it may very well be NULL)
    temp = current->next->next;
    // is there a next src+dst pair?
    bool have_next = temp != NULL;
    // if there is, do the forward pointers, otherwise null
    current->next->next = have_next ? temp->next : NULL;
    current->next       = have_next ? temp : NULL;
    // move forward
    current = temp;
  }
}

// utility function for deleting a list
void delete_list(list_item* first)
{
  if (first->next != NULL)
    delete_list(first->next);
  delete first;
}

void main() 
{ 
  cout.setf(ios_base::boolalpha);

  // test 1 - copy single element with rand=null
  list_item* first = new list_item;
  first->next = first->rand = NULL;

  list_item* copied;
  deep_copy(first, copied);
  
  cout << "test 1 - copy single element with rand=null: " << (copied->next == NULL) << " " << (copied->rand == NULL) << endl;
  delete_list(first);
  delete_list(copied);

  // test 2 - copy single element with rand=self
  first = new list_item;
  first->next = NULL;
  first->rand = first;

  deep_copy(first, copied);

  cout << "test 2 - copy single element with rand=self: " << (copied->next == NULL) << " " << (copied->rand == copied) << endl;
  delete_list(first);
  delete_list(copied);

  // test 3 - copy two elements with mutually referencing rand's
  first = new list_item;
  list_item* second = new list_item;
  first->next = first->rand = second;
  second->next = NULL;
  second->rand = first;

  deep_copy(first, copied);

  cout << "test 3 - copy two elements with mutually referencing rand's: " <<
    (copied->rand == copied->next) << " " <<
    (copied->next->next == NULL) << " " <<
    (copied->next->rand == copied) << " " << endl;
  delete_list(first);
  delete_list(copied);

  getchar();
}