leetcode138. Copy List with Random Pointer

Kross 发布于2019-08-16 10:47 / 2157人阅读

摘要：题目要求假设存在这样一个链表，在链表的每一个节点中，除了记录了自身值和指向下一个节点的指针，还有一个随机指针指向链表中任意一个节点。所以可以在两次遍历后完成任务。最后一圈遍历，我们调整指针，恢复原链表和塑造新链表。

题目要求

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 map = new HashMap();
        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;
    }

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

混合云专线服务 Pointer 138vps ddd138 Leetcod

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/70454.html

LeetCode[138] Copy List with Random Pointer

LeetCode[138] 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. Return a deep copy of t...

novo 2019-08-14 15:57 评论0 收藏0
LeetCode 138：复制带随机指针的链表 Copy List with Random Poin

摘要：给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深拷贝。提示你必须返回给定头的拷贝作为对克隆列表的引用。确定随机节点的关系之后再拆分链表。其时间复杂度为，空间复杂度为。给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深拷贝。 A linked list is g...

entner 2019-08-19 10:13 评论0 收藏0
LeetCode 138：复制带随机指针的链表 Copy List with Random Poin

摘要：给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深拷贝。提示你必须返回给定头的拷贝作为对克隆列表的引用。确定随机节点的关系之后再拆分链表。其时间复杂度为，空间复杂度为。给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深拷贝。 A linked list is g...

Lucky_Boy 2019-07-31 11:31 评论0 收藏0
[Leetcode] Copy List with Random Pointer 复制随机指针

摘要：栈迭代复杂度时间空间如果不算新链表的空间则是思路由于随机指针有可能产生环路，我们不能直接沿着随机指针的方向一个一个复制。同时我们又不能沿着指针直接复制，因为我们不知道随机指针所指向的新节点是哪个。 Copy List with Random Pointer A linked list is given such that each node contains an additiona...

Olivia 2019-08-14 12:25 评论0 收藏0
[LintCode/LeetCode] Copy List with Random Pointer

摘要：大体意思就是，先复制到，顺便将所有的放在再复制所有的到，顺便将所有的放在最后令，令，将和分离，返回的头结点 Problem 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. ...

Jacendfeng 2019-08-14 15:32 评论0 收藏0