小弟提供一数据结构题目，以供娱乐

flyv

现有一链表，拥有一个指向下一个元素的指针pNext,还有一个随机指向的指针pRandom,现在需要拷贝这样一个链表，请给出最优解。
假设数据结构如下：
struct Node
{
  int data;
  Node* pNext;
  Node* pRandom;
};

kypck

pRandom应该是指想链表内的一个node，这个条件说明确点。
还有，最优解，算法复杂度最优，时间最优还是特定情况下实际执行速度最优？

芙ZM

随机指向的指针
有意思,研究研究

halei

我记得你说，你为了努力回答任何新手问题的。.....
    怎么变成考新手题目了?

flyv

我也要发展的嘛，我不发展，怎么回答新手问题呢？

flyv

没人做么？哎……

aear

下面是个 3n 的算法：
假设是不循环的，也就是最后一个pNext是NULL, 写的仓促，希望大家能看的明白。
其实 2N 的算法也有，不过前提是 sizeof(int) = sizeof(Node *)，需要Data储存一个指针，或者Data有取值范围。也许有其他 2N 算法不需要Data的，不过偶没想出来。不过循环链表到是有不需要前提条件的2N算法。至于N的算法。。。。。。。。那就不知道了。

Node* copy(Node* pHead)
{
    if(!pHead) return NULL;

    Node * pCurNode = pHead;
    Node * pTemp;

    do
   {
        pTemp = new Node();
        pTemp ->data = pCurNode ->data;
        pTemp ->pNext = pCurNode ->pRandom;
        pCurNode ->pRandom = pTemp;      
    } while(pCurNode = pCurNode->pNext)

    pCurNode = pHead;
    do {
        pCurNode->pRandom->pRandom = pCurNode->pRandom->pNext->pRandom;
    } while(pCurNode = pCurNode->pNext);

    pCurNode = pHead;
    Node TempHead;
    pTemp = &TempHead;
    do {
        pTemp->pNext = pCurNode->pRandom;
        pTemp = pCurNode->pRandom;
        pCurNode->pRandom = pCurNode->pRandom->pNext;
    } while(pCurNode = pCurNode->pNext);

    return TempHead->pNext;
}

芙ZM

认真学习ing

flyv

假如旧链表是ABCDEF……
新构造的链表是A'B'C'D'E'F'……

构造新链表是使得A->pNext = A';A'->pNext = B;
即变换为如下链表
AA'BB'CC'DD'EE'FF'……

那么 A'->pRandom = A->pRandom->pNext;
依此类推

最后分拆链表

故得

这个方法或许比较明了一点，不过还是O(N)的算法。

smile636

呵呵顶一个~