[LintCode/LeetCode] Copy List with Random Pointer

Jacendfeng 发布于2019-08-14 15:32 / 3548人阅读

摘要：大体意思就是，先复制到，顺便将所有的放在再复制所有的到，顺便将所有的放在最后令，令，将和分离，返回的头结点

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.

Challenge

Could you solve it with O(1) space?

Note

因为O(1) space，所以no hashtable。新建两个结点n1 n2，令n1 = head，向后循环，同时不断复制n2到n1.next；再放回头结点，循环第二次，复制n2.random到n1.random.next，再放回头结点；再建立第三个结点n3 = n2，循环第三次，令n1 n2分离，返回头结点n3，结束。

大体意思就是，先复制n1到n2，顺便将所有的n2放在n1.next；再复制所有的n1.random到n2.random，顺便将所有的n2.random放在n1.random.next；最后令n3 = n2，令n1 = n1.next.next, n2 = n2.next.next，将n1和n2分离，返回n2的头结点n3.

Solution

public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) return null;
        RandomListNode n1 = head, n2, n3;
        while (n1 != null) {
            n2 = new RandomListNode(n1.label);
            n2.next = n1.next;
            n1.next = n2;
            n1 = n1.next.next;
        }
        n1 = head;
        n2 = n1.next;
        while (n1 != null) {
            n2.random = n1.random == null ? null : n1.random.next;
            n1 = n1.next.next;
            n2 = n1 == null ? null : n2.next.next;
        }
        n1 = head;
        n2 = n1.next;
        n3 = n2;
        while (n1 != null) {
            n1.next = n1.next.next;
            n2.next = n2.next == null ? null : n2.next.next;
            n1 = n1.next;
            n2 = n2.next;
        }
        return n3;
    }
}

云服务器 GPU云服务器 Pointer copy php @copy python copy

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

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

[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
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
[LintCode/LeetCode] Flatten Binary Tree to Linked

Problem Flatten a binary tree to a fake linked list in pre-order traversal.Here we use the right pointer in TreeNode as the next pointer in ListNode. Example 1 1 ...

TNFE 2019-08-14 15:12 评论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