一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1415|回复: 5
收起左侧

[算法题] 一道LeetCode算法题求助

[复制链接] |试试Instant~ |关注本帖
zhcxyz 发表于 2014-3-3 05:56:14 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
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}
*/

求哪位大神给我解答一下,问题出在哪里啊? 纠结了一下午了><
一剑终情 发表于 2014-3-3 06:47:29 | 显示全部楼层
本帖最后由 一剑终情 于 2014-3-2 16:55 编辑

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

使用道具 举报

一剑终情 发表于 2014-3-3 07:46:15 | 显示全部楼层
  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的特殊情况。
回复 支持 反对

使用道具 举报

 楼主| zhcxyz 发表于 2014-3-3 08:25:09 | 显示全部楼层

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

使用道具 举报

dhtim135 发表于 2014-3-5 11:55:05 | 显示全部楼层
我遇到过一样的问题
主要还是reference没搞清楚
设置新的random pointer时一定是新创建的node
回复 支持 反对

使用道具 举报

landuostorm 发表于 2014-3-5 21:44:37 | 显示全部楼层
今天做到这个题了。分享一个思路
假设原链表为[1,2,3,4]
遍历并为这个链表做一个“影子”, 操作后链表为[1,1,2,2,3,3,4,4]
设置影子的random pointer (若node->random不为null,node->next->random = node->random->next)
最后拆分
这样做的好处是不需要额外空间,但是需要遍历两次链表

评分

2

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 16:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表