一道LeetCode算法题求助

LeetCode上名为 Copy List with Random Pointer的题目。
题目要求是：
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

我的想法是借助哈希表来实现，每次在新的List中添加一个Node之后就按照<OldNode, NewNode>的pair存进哈希表里面，后面再为新的LinkedList创建Node的时候，看看next，random两个Point所指向的Node是不是已经在先前创建过了，如果是就直接用创建好的，不然就新建一个。以下是我的实现代码：
/**
* Definition for singly-linked list with a random pointer.
* class RandomListNode {
*     int label;
*     RandomListNode next, random;
*     RandomListNode(int x) { this.label = x; }
* };
*/
public class Solution
{
    public RandomListNode copyRandomList(RandomListNode head)
    {
                if (head == null)
                        return null;

        RandomListNode newhead = new RandomListNode(head.label);
                if (head.next == null)
                {
                        newhead.next = head.next;
                        newhead.random = head.random;
                        return newhead;
                }

                HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
                map.put(head, newhead);
                map.put(null,null);

                RandomListNode pOld = head, pNew;

                while(pOld!=null)
                {
                        if (map.containsKey(pOld))
                                pNew = map.get(pOld);
                        else
                        {
                                pNew = new RandomListNode(pOld.label);
                                map.put(pOld, pNew);
                        }

                        if (map.containsKey(pOld.next))
                                pNew.next = map.get(pOld.next);
                        else
                        {
                                pNew.next = new RandomListNode(pOld.next.label);
                                map.put(pOld.next, pNew.next);
                        }

                        if (map.containsKey(pOld.random))
                                pNew.random = map.get(pOld.random);
                        else
                        {
                                pNew.random = new RandomListNode(pOld.random.label);
                                map.put(pOld.random, pNew.random);
                        }
                        pOld = pOld.next;
                }

                return newhead;
    }
}

没有Accept，报错如下：
/*
Submission Result: Wrong Answer

Input:        {-1,-1}
Output:        Random pointer of node with label -1 points to a node from the original list.
Expected:        {-1,-1}
*/

求哪位大神给我解答一下，问题出在哪里啊？ 纠结了一下午了><

怎么你复制粘贴下来所有指针的星号都不见了
原来是Java、、不懂了但是从OJ给的信息来看，指针应当指向新list的，但是你的指针指向原来的list了

1. if (head.next == null)
   
2.                 {
   
3.                         newhead.next = head.next;
   
4.                         newhead.random = head.random;
   
5.                         return newhead;
   
6.                 }

复制代码

问题出在这几行。newhead.random = head.random ，在head.random不等于null的时候，是原list中的node。

而且这几行毫无意义，这几步都在后面的while循环里处理掉了，没必要加这几行处理list中只有两个node的特殊情况。

一剑终情 发表于 2014-3-3 07:46
问题出在这几行。newhead.random = head.random ，在head.random不等于null的时候，是原list中的node。

...

试了一下，果然是这里的问题！ 太感谢了，纠结了好久。 自己吃了不少special case不处理的亏，所以会特地多想一下是不是要处理special case，这里反倒是想多了。 感谢！！

我遇到过一样的问题
主要还是reference没搞清楚
设置新的random pointer时一定是新创建的node

今天做到这个题了。分享一个思路
假设原链表为[1,2,3,4]
遍历并为这个链表做一个“影子”， 操作后链表为[1,1,2,2,3,3,4,4]
设置影子的random pointer (若node->random不为null,node->next->random = node->random->next)
最后拆分
这样做的好处是不需要额外空间，但是需要遍历两次链表