// Linked List with Random Pointer - Duplicate and Reverse
// Assumption: No two random pointers are pointing to the same node (except if NULL)
//

#include <stdio.h>

//#define DEBUG_PRINT

#define SIZEOFARRAY(arr)  (sizeof((arr))/sizeof((arr)[0]))

typedef struct Node
{
  struct Node *pNext;
  struct Node *pRandom;
  int data;
} node_t;

struct Node*   CreateList(int nData, int  *pData, int *pRandom);
void           PrintList(struct Node *pHead, char *pContext);
struct Node*   FreeList(struct Node *pList);
struct Node*   DuplicateList(struct Node *pList);
struct Node*   ReverseList(struct Node *pList);

int main(int argc, char *args[])
{
  int dataSize, randomSize;
  int *pData, *pRandom;
  struct Node *pList = NULL, *pNewList = NULL; 

  int data1[] = {10, 20, 30, 40, 50};
  int random1[] = {40, -1, -1, -1, 20};

  printf("\n");

  dataSize = SIZEOFARRAY(data1); pData = (int *) data1;
  randomSize = SIZEOFARRAY(random1); pRandom = (int *)random1;
  if (dataSize != randomSize) { printf("ERROR: Invalid Input\n"); return -1; }
  pList = CreateList(dataSize, pData, pRandom); PrintList(pList, "Input"); 
  pNewList = DuplicateList(pList); 
  PrintList(pNewList, "Copy"); 
  pNewList = ReverseList(pNewList);
  PrintList(pNewList, "Reverse"); 
  pNewList = FreeList(pNewList); 
  pList = FreeList(pList);

  return 0;
}

struct Node*  ReverseList(struct Node *pList)
{
  struct Node *pMover, *pMoverNext, *pNewHead;
  struct Node *pTrav, *pTravRandom, *pRandHead; 
  struct Node *pReverseTail = NULL;
  int isHead = 0;

  // Reverse Next Pointers
  for(pMover = pList, pNewHead = NULL; pMover; pMover = pMoverNext)
  {
    pMoverNext = pMover->pNext;
    pMover->pNext = pNewHead;
    pNewHead = pMover;
  }

  pReverseTail = (struct Node*) malloc(sizeof(struct Node));
  pReverseTail->pNext = pReverseTail->pRandom = pReverseTail;
  pReverseTail->data = 0;

  for (pMover = pNewHead; pMover; pMover = pMoverNext)
  {
    pMoverNext = pMover->pNext;

    if (NULL == pMover->pRandom) continue;

    // Check if this is head in random-pointer linked list
    isHead = 1;
    for (pTrav = pNewHead; isHead && pTrav; pTrav = pTrav->pNext)
    {
      if (pTrav->pRandom == pMover) { isHead = 0; break; }
    }

    if (isHead)
    {
      // If already reversed (i.e. reversed list head), then do not do it again
      for (pTrav = pMover; isHead && pTrav; pTrav = pTrav->pRandom)
      {
        if (pTrav == pReverseTail) { isHead = 0; break; }
      }
    }

#ifdef DEBUG_PRINT
    printf("DEBUG: IsHead(%d) = %d\n", pMover->data, isHead);
#endif

    if (isHead)
    {
      for(pTrav = pMover, pRandHead = pReverseTail; pTrav; pTrav = pTravRandom)
      {
        pTravRandom = pTrav->pRandom;
        pTrav->pRandom = pRandHead;
        pRandHead = pTrav;
      }
    }
  }

  // Reset all 'Reverse Tail Head' pointers to NULL
  //
  for (pMover = pNewHead; pMover; pMover = pMover->pNext)
  {
    if (pMover->pRandom == pReverseTail) pMover->pRandom = NULL;
  }

  if (NULL != pReverseTail) free(pReverseTail);

  return pNewHead;
}

struct Node*  DuplicateList(struct Node *pList)
{
  struct Node  *pNode, *pMover, *pHead, *pMoverNext;
  
  pHead = NULL; pNode = NULL; 
  pMover = NULL; pMoverNext = NULL;
  
  // Create duplicate nodes and 
  // insert just after the original node in the same list
  for (pMover = pList; pMover; pMover = pMoverNext)
  {
    pMoverNext = pMover->pNext;

    pNode = (struct Node *) malloc(sizeof(struct Node));
    
    if (NULL == pNode) goto cleanup;
    if (NULL == pHead) pHead = pNode;
    
    pNode->data = pMover->data;
    pNode->pRandom = NULL;
    pNode->pNext = pMover->pNext;
    pMover->pNext = pNode;
  }

  // Set Random Pointers for new nodes
  for (pMover = pList; pMover; pMover = pMover->pNext->pNext)
  {
    pMover->pNext->pRandom = pMover->pRandom ? pMover->pRandom->pNext : NULL;
  }

  // Split the combined list
  for (pMover = pList; pMover; pMover = pMover->pNext)
  {
    pMoverNext = pMover->pNext;
    pNode = pMoverNext->pNext;

    pMover->pNext = pNode;
    pMoverNext->pNext = pNode ? pNode->pNext : NULL;
  }

  return pHead;

cleanup:
  printf("ERROR: Original List is modified and not restorable!\n");
  return NULL;
}

struct Node*  CreateList(int nData, int  *pData, int *pRandom)
{
  struct Node *pHead;
  struct Node *pNode, *pTemp;
  int i;

  if (NULL == pData || nData <= 0) return NULL;
 
  pTemp = NULL; pNode= NULL; pHead = NULL;

  for (i = 0; i < nData; i++)
  {
    pNode = (struct Node *) malloc(sizeof(struct Node));
    
    if (NULL == pNode) goto cleanup;
    if (NULL == pHead) pHead = pNode;
    
    pNode->data = pData[i];
    pNode->pNext = NULL;
    pNode->pRandom = NULL;

    if (NULL != pTemp) { pTemp->pNext = pNode; }
    pTemp = pNode;
  }

  for (i = 0, pNode = pHead; i < nData; i++, pNode = pNode->pNext)
  {
    for (pTemp = pHead; pTemp; pTemp = pTemp->pNext)
    {
      if (pTemp->data == pRandom[i]) break;
    }

    pNode->pRandom = pTemp; 
  }

  return pHead;

cleanup:
  FreeList(pHead);
  return NULL;
}

void PrintList(struct Node *pList, char *pContext)
{
  struct Node *pMover = pList;

  printf("List (%s) :  ", pContext);
  if (NULL == pList) printf(":: EMPTY ::");

  while(pMover)
  {
#ifdef DEBUG_PRINT
    printf("0x%08X = %d (0x%08X = %d), ", pMover, pMover->data, 
      pMover->pRandom, pMover->pRandom ? pMover->pRandom->data : -1);
#else
    printf("%d (%d), ", pMover->data, pMover->pRandom ? pMover->pRandom->data : -1);
#endif

    pMover = pMover->pNext;
  }
  printf("\n");
}

struct Node* FreeList(struct Node *pList)
{
  struct Node *pCurrent, *pNext;

  pCurrent = pList;

  while (pCurrent)
  {
    pNext = pCurrent->pNext;
    pCurrent->pNext = NULL;
    free(pCurrent);
    pCurrent = pNext;
  }

  return NULL;
}

List (Input) :  10 (40), 20 (-1), 30 (-1), 40 (-1), 50 (20), 
List (Copy) :  10 (40), 20 (-1), 30 (-1), 40 (-1), 50 (20), 
List (Reverse) :  50 (-1), 40 (10), 30 (-1), 20 (50), 10 (-1),