某人MSN上的据说是正确答案

程序代码：

如何copy pRand指针是关键，我当时的第一感觉就是要利用两个指针域来让新链表和原链表有关联。于是考虑把新生成的节点，插入到源节点和后续节点中。比如ABC是源链表，当生成A节点的新节点A'后，插入AB之间，变成AA'BC。那样最后链表变成AA'BB'CC', 设置A‘的pRand一定被A的pRand节点的pNext域所指向。
typedef struct node
{
 int _value;
 node* _pNext;
 node*     _pRand;
}NODE;

NODE* NODECopy(NODE* head)
{
 if (0 == head) return 0;
 NODE* pOrg = 0;
 NODE* pNew = 0;
 for (pOrg = head; pOrg != 0; pOrg = pOrg->_pNext->_pNext)
 {
  pNew = new NODE;
  pNew->_value = pOrg->_value;
  
  pNew->_pNext = pOrg->_pNext;
  pOrg->_pNext = pNew;
  
  pNew->_pRand = 0;
 }
 
 NODE* pNewHead = head->_pNext;
 pOrg = head;
 while (pOrg != 0)
 {
  pNew = pOrg->_pNext;
  pNew->_pRand = pOrg->_pRand->_pNext;
  pOrg = pNew->_pNext;
 }
 pOrg = head;
 pNew = head->_pNext;
 
 while ( pNew->_pNext != 0)
 {
  pOrg->_pNext = pOrg->_pNext->_pNext;
  pNew->_pNext = pNew->_pNext->_pNext;
 
  pOrg = pOrg->_pNext;
  pNew = pNew->_pNext;
 }
 pOrg->_pNext = 0;
 pNew->_pNext = 0;
 return pNewHead;
}