外星人源码论坛 首页 编程经验

leetcode138. Copy List with Random Pointer

2018-3-5 06:46
原作者: 外星人源码网 来自: 外星人源码网 收藏 分享 邀请

题目要求 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.Return a deep

题目要求

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.

Return a deep copy of the list.

假设存在这样一个链表,在链表的每一个节点中,除了记录了自身值和指向下一个节点的指针,还有一个随机指针指向链表中任意一个节点。现在要求深度复制这份链表,在不改变原链表内容的情况下,创建一组新的对象,该组对象中的值和原链表中的值相同。

思路一:map

因为任意节点指针的值在一遍遍历中是无法复制的。所以我们可以基本确定至少需要两次遍历才能够充分的复制链表。那么在第一次遍历的时候,我们采用什么样的数据结构来记录第一次遍历的值呢?最直观的思路是使用map,第一次遍历时我们访问next指针,将当前对象和当前对象的复制对象作为key-value值存入map中。第二次遍历时,我们可以一边调整复制对象的next指针,一边调整复制对象的random指针,这两个指针指向的都将是map中源对象的复制对象。所以可以在两次遍历后完成任务。

    public RandomListNode copyRandomList(RandomListNode head) {
        if(head==null) return null;
        Map<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
        RandomListNode temp = head;
        while(temp!=null){
            map.put(temp, new RandomListNode(temp.label));
            temp = temp.next;
        }
        
        temp = head;
        while(temp!=null){
            RandomListNode cur = map.get(temp);
            cur.next = map.get(temp.next);
            cur.random = map.get(temp.random);
            temp = temp.next;
        }
        return map.get(head);
    }

思路二:利用链表的特性

那么我们有没有可能在不使用map的情况下通过旧节点实现对新节点的检索?答案是肯定的。我们可以充分利用链表的特性来保存对新的复制节点的指针。第一圈遍历时,我们可以将复制的节点插入至被复制的节点的后面。这样我们就可以通过旧节点的next值找到新节点。在第二圈遍历的时候,我们可以依次更新复制节点的random指针,将其指向新的复制节点。最后一圈遍历,我们调整next指针,恢复原链表和塑造新链表。

    public RandomListNode copyRandomList2(RandomListNode head) {
        if(head==null) return null;
        RandomListNode current = head, copyHead = null, copyCurrent = null;
        
        while(current!=null){
            RandomListNode temp = new RandomListNode(current.label);
            temp.next = current.next;
            current.next = temp;
            current = current.next.next;
        }
        
        current = head;
        while(current!=null){
            if(current.random!=null){
                current.next.random = current.random.next;
            }
            current = current.next.next;
        }
        
        current = head;
        copyCurrent = copyHead = head.next;
        head.next = head.next.next;
        while(current != null){
            current.next = current.next.next;
            copyCurrent.next = copyCurrent.next.next;
            copyCurrent = copyCurrent.next;
            current = current.next;
        }
        return copyHead;
    }

鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

粉丝 阅读28 回复0
上一篇:
在 Forge Viewer 里加入自订义线发布时间:2018-03-05
下一篇:
karma如何与测试框架合作发布时间:2018-03-05
国内最专业的源码技术交流社区
全国免费热线电话

0373-5171417

周一至周日9:00-23:00

反馈建议

admin@eenot.com 在线QQ咨询

扫描二维码关注我们