[Leetcode] Copy List with Random Pointer 复制随机指针

Olivia 发布于2019-08-14 12:25 / 2547人阅读

摘要：栈迭代复杂度时间空间如果不算新链表的空间则是思路由于随机指针有可能产生环路，我们不能直接沿着随机指针的方向一个一个复制。同时我们又不能沿着指针直接复制，因为我们不知道随机指针所指向的新节点是哪个。

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 the list.

栈迭代 复杂度

时间 O(N) 空间 O(N) 如果不算新链表的空间则是O(1)

思路

由于随机指针有可能产生环路，我们不能直接沿着随机指针的方向一个一个复制。同时我们又不能沿着next指针直接复制，因为我们不知道随机指针所指向的新节点是哪个。这里有个技巧，我们把复制的表一对一的插在旧表的每个节点后面，这样在第二次遍历链表时，我们就肯定知道随机指针指向的新节点是哪个了，肯定是旧节点随即指针指向的旧节点的下一个节点。然后我们再遍历一遍，把新旧两个链表分割开来就行了。

代码

public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if(head==null) return null;
        RandomListNode n1 = head;
        RandomListNode n2;
        // 生成新节点并接在旧节点后面
        while(n1!=null){
            n2 = new RandomListNode(n1.label);
            n2.next = n1.next;
            n1.next = n2;
            n1 = n1.next.next;
        }
        // 给新节点的random字段赋值
        n1 = head;
        n2 = n1.next;
        while(n1!=null){
            n2.random = n1.random != null ? n1.random.next : null;
            n1 = n1.next.next;
            n2 = n1 != null ? n2.next.next : null;
        }
        n1 = head;
        n2 = n1.next;
        RandomListNode res = n2;
        // 将新旧节点分开
        while(n1!=null){
            n1.next = n1.next.next;
            n2.next = n2.next != null ? n2.next.next : null;
            n1 = n1.next;
            n2 = n2.next;
        }
        return res;
    }
}

专线服务私有云 random随机数 random生成随机数随机数math_random Pointer

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

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

leetcode138. Copy List with Random Pointer

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

Kross 2019-08-16 10:47 评论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
[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
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