mpweixin用户普通 2024年5月14日上午11:56

使用hashmap打卡成功

0 赞同 0 条回复

Serena 普通 2023年9月5日下午5:21

时间n 空间n
/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;

public Node(int val) {
    this.val = val;
    this.next = null;
    this.random = null;
}

}
*/
class Solution {
Map<Node,Node> cachedNode=new HashMap<Node,Node>();
public Node copyRandomList(Node head) {

    if(head==null){
        return null;
    }
    if(!cachedNode.containsKey(head)){
        Node nodeNew=new Node(head.val);
        cachedNode.put(head,nodeNew);
        nodeNew.next=copyRandomList(head.next);
        nodeNew.random=copyRandomList(head.random);
    }
    return cachedNode.get(head);
}

}

0 赞同 0 条回复

Prime 普通 2023年9月5日下午3:40

时间复杂度:O(n)
空间复杂度:O(1)

    
# Definition for a Node.
class Node:
    def __init__(self, x, next=None, random=None):
        self.val = int(x)
        self.next = next
        self.random = random
"""
class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        if not head:
            return None
        # 复制链表节点
        cur = head
        while cur is not None:
            next = cur.next
            cur.next = Node(cur.val)
            cur.next.next = next
            cur = next
        # 复制random指针
        cur = head
        while cur != None:
            curNew = cur.next
            curNew.random = cur.random.next if cur.random else None
            cur = cur.next.next
        # 拆分链表
        cur = head 
        head_new = head.next
        curNew = head.next
        while cur:
            cur.next = cur.next.next
            cur = cur.next
            curNew.next = cur.next if cur else None
            curNew = curNew.next

        return head_new

“””

0 赞同 0 条回复

梧葳普通 2023年9月1日上午12:31

普通节点复制—->随机节点指向复制—->最后进行链表的拆分
“””
class Solution {
public:
Node* copyRandomList(Node* head) {
if (head NULL) {
return NULL;
}
// 复制链表节点，如1->2>3为:1->1′->2->2′->3->3′
Node *cur = head;
while (cur != NULL) {
Node *newNode = new Node(cur->val);
newNode->next = cur->next;
cur->next = newNode;
cur = newNode->next;
}
// 复制random节点,同上，指向原random的next即可
cur = head;
while (cur != NULL && cur->next != NULL) {
Node *next = cur->next;
next->random = ((cur->random NULL) ? NULL : cur->random->next);
cur = next->next;
}
// 拆分节点，把两条链表分开
cur = head;
Node *head_new = head->next;
Node *cur_new = head->next;
while (cur != NULL && cur->next != NULL) {
cur->next = cur_new->next;
cur = cur_new->next;
if (cur_new->next != NULL) {
cur_new->next = (cur->next NULL ? NULL : cur->next);
cur_new = cur_new->next;
}
}

    return head_new;
}

};
“””

0 赞同 0 条回复

黎明之前普通 2023年8月28日上午12:16

//链表中有next指针和random指针要将两个指针复制到单个数字后面
//之后再进行分割
if(head NULL)
return NULL;
Node *cur = head;
//复制链表节点
while(cur NULL)
{
Node *next = cur ->next;
cur->next = new Node(cur->val);
cur->next ->next = next;
cur = next;
}
//复制随机节点
cur = head;
while(cur !=NULL)
{
Node *cur = cur->next;
curNew->random= cur->random?cur->random ->next:NULL;
cur = cur->next->next;
}
//拆分
Node *headNew= head->next;
cur = head;
Node *curNew = head->next;
while(cur)
{
cur ->next = cur->next->next;
cur = cur ->next;
curNew->next – cur?cur->next:NULL;
curNew = curNew->next;

}
return headNew;

}

0 赞同 0 条回复

我一定要坚持打卡普通 2023年8月27日上午8:43

思路

解题思路

这里因为有一个random指针指向，所以在复制的时候，需要复制random指针的前向节点和random指向的节点，所以不能像单链表复制那样，直接从头到尾进行复制；

这里对原链表先进行扩充，让链表从A->B->C 变成A->A1->B->B1->C->C1 其中X1 表示对原数据的复制

复制原来链表中的random节点，使得原链表中的random节点复制到新复制的X1节点上

在将复制好的链表进行拆分，变成新的复制成品和原链表两个链表并返回新链表地址 A->A1->B->B1->C->C1 变成 A->B->C A1->B1->C1

详细思路见这个链接里边的第二种方法

138. 复制带随机指针的链表 – 力扣（LeetCode）

还有一种方法使用哈希表进行实现这里没看

解题方法

解题方法

先复制链表【循环时逐个改变原链表节点的指针使其指向新建的节点并改变新建节点的next指向原节点的next使其连贯，直至复制到链表为空】

设定新复制的节点的random节点，random节点应该是原链表节点的random指向的节点的next，因为新复制的节点在原链表节点的后一个代码实现的话是 cur.next.random = cur.ramdom.next

拆分链表，使得 A->A1->B->B1->C->C1 变成 A->B->C A1->B1->C1 新建两个头指针指向两个拆分好的链表，返回新的头指针

复杂度

时间复杂度:

时间复杂度： $O(n)$

m 和 n 分别是链表的长度

空间复杂度:

空间复杂度： $O(n)$

Code

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {



        if(head==null){
            return null;
        }

        // 先复制链表
        // 让链表从A->B->C 变成A->A1->B->B1->C->C1 //这里是对数据对复制， 然后在进行拆分

        // 先保存当前节点的next，再在next前边增加一个新的节点并且赋值为cur.val
        Node cur = head;
        while(cur != null){
            Node next = cur.next;
            cur.next = new Node(cur.val);//设定val值
            cur.next.next = next;       // 设定next值
            cur= next;                  //cur后移，移动到原链表的下一个节点上继续进行复制
        }

        //保存完成原来的节点之后，修改新复制数据的random值，让他指向正确的数据
        // 这里要根据原来数据的random设定新的复制出的数据的random
        // A->A1->B->B1->C->C1  新复制的数据的random =当前指针的random指向的数据的next
        // 【因为新插入的数据  在原来数据的后边，所以要加一个next指向】
        cur = head;
        while(cur!= null){
            // cur.next.random = cur.random.next;//这里因为题目中提到可能为null
            //不能按照上边的写法，应该重写一下
            Node newNode = cur.next;
            newNode.random = cur.random == null ? null:cur.random.next;
            cur = cur.next.next; 
        }

        // 链表拆分，将一个链表拆分成两个分离的链表
        // A->A1->B->B1->C->C1 变成 A->B->C  A1->B1->C1 
        // 注意这里在更改的时候,已经改变了cur.next  一定要注意这一点

        Node headNew = head.next;// 指向新复制的链表的头结点也就是A1
        cur  =head;// 用来改变旧链表的next指向
        Node curNew = headNew;// 用来改变新链表的节点的next
        while(cur!=null){
            cur.next = cur.next.next;// 这里cur.next 已经从A1指向 B
            cur = cur.next;// 直接让cur 再从B继续

            // curNew.next  = cur.next;
            // 这里cur 已经从A指向 B.直接让curNew指向B1即可【
            // 注意cur可能为null也就是cur已经指向了最有一个节点,但是新链表还没更改,所以要单独设定】
            curNew.next = cur ==null? null:cur.next;
            curNew =curNew.next;
        }
        return headNew;

    }

}

0 赞同 0 条回复

Di questa storia sempre a lie to 普通 2023年8月24日上午12:19

class Solution {
public:
Node* copyRandomList(Node* head) {
if(headnullptr) {
return nullptr;
}
for(Node* node =head; node !=nullptr; node=node->next->next){
Node* nodeNew = new Node(node->val);
nodeNew->next = node->next;
node->next = nodeNew;
}
for(Node* node = head; node!=nullptr; node=node->next->next){
Node* nodeNew = node->next;
nodeNew->random = (node->random!=nullptr)? node->random->next:nullptr;
}
Node* headnew = head->next;
for(Node* node =head; node!=nullptr;node=node->next){
Node* nodeNew=node->next;
node->next = node->next->next;
nodeNew->next=(nodeNew->next != nullptr)? nodeNew->next->next : nullptr;
}
return headnew;
}
};
时间复杂度： O(N)
空间复杂度：O(N)

0 赞同 0 条回复

小火普通 2023年8月22日下午5:28

哈希表+回溯（题解中的方法）
时间复杂度：o(n)
空间复杂度：o(n)

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    unordered_map cachedNode;

    Node* copyRandomList(Node* head) {
        if(head == NULL) {
            return head;
        }

        if(!cachedNode.count(head)) {
            Node* headNew = new Node(head->val);
            cachedNode[head] = headNew;
            headNew->next = copyRandomList(head->next);
            headNew->random = copyRandomList(head->random);
        }
        return cachedNode[head];
    }
};

0 赞同 0 条回复

谁仁普通 2023年8月22日下午2:10

struct node * randomList(struct node * head)
{
//判断链表是否为空
if(head NULL)
{
return NULL;
}

//插入复制节点
struct node * curr =head;

while( curr!= NULL)
{
    struct node * cpy = (struct node*)malloc(sizeof(struct node*));
    cpy->val = curr->val;//赋值临时链表的值
    cpy->next = curr->next;//将临时链表的next节点复制当前的下一个节点，以便等会重新将该链接连接到原链表 1-1
    cpy->random = NULL;//赋值随机指针为空，等会有用

    curr->next = cpy;//将下当前的next指针链接上复制的指针，插入临时
    curr = cpy->next;//续上1-1即往下走当前的指针更新为下一个待复制节点，即往后走，变成的是我们//curr --curr->next=cpy->next --cpy(插入） --cpy->next
    //  |____________________________ _______> ______|
}

//复制random指针，处理到我们cpy里面
while(curr != NULL)
{
    struct node* cpy = curr->next;
    if(curr->random != NULL)
    {
        cpy->random = curr->random->next;//往下走，赋值random到curr
    }
    curr = cpy->next;
}
//拆解链表，重新回归
curr = head;
struct node* newhead = head->next;
while(curr ！= NULL)
{
    struct node* cpy = curr->next;
    curr->next = cpy->next;
    if(cpy->next != NULL)
    {
        cpy->next = cpy->next->next;//同样操作，我们继续要往下遍历复制链表，冰洁分离出来
    }
    curr = curr->next;
}
return newhead;

}//时间复杂度为O(n)，空间复杂度为O(1)

0 赞同 0 条回复

sc_Yang 普通 2023年8月20日下午5:07

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        // Node* node = new Node();
        if(head == NULL){
            return NULL;
        }
        // 拷贝各节点值和其next顺序
        for(Node* node=head; node!=NULL; node = node->next->next){
            Node* nodeNew = new Node(node->val);
            nodeNew->next = node->next;
            node->next = nodeNew;
        }
        // 拷贝各节点的随机指针random
        for(Node* node=head; node!=NULL; node=node->next->next){
            Node* nodeNew = node->next;
            if(node->random){
                nodeNew->random = node->random->next; // 新链子的随机节点应该在原随机位点的后一个
            }else{
                nodeNew->random = NULL;
            }   
        }
        // 将拷贝完的新节点都拆出来
        Node* headNew = head->next;
        for(Node* node=head; node!=NULL; node=node->next){
            Node* nodeNew = node->next;
            node->next = node->next->next;
            if(nodeNew->next){
                nodeNew->next = nodeNew->next->next;
            }else{
                nodeNew->next = NULL;
            }
        }
        return headNew;
    }
};

0 赞同 0 条回复

辰北、普通 2023年8月20日下午3:44

class Solution {//先用cur走一遍，链式存储一下，第二次map【random】就不会指向空值。
public:
Node* copyRandomList(Node* head) {
if(headnullptr)return nullptr;

   Node* cur =head;
//    Node* dum= new Node(0),*pre =dum;
unordered_map<Node*,Node*> map;

   while(cur!=nullptr){
       map[cur] =new Node(cur->val);
       cur=cur->next;
   } 
   cur=head;
   while(cur!=nullptr){
       map[cur]->next=map[cur->next];
       map[cur]->random=map[cur->random];
       cur=cur->next;
   }
   return map[head];
}

};
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;

Node(int _val) {
    val = _val;
    next = NULL;
    random = NULL;
}

};
/
/
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;

Node(int _val) {
    val = _val;
    next = NULL;
    random = NULL;
}

};
/
// class Solution {
// public:
// Node copyRandomList(Node* head) {//遍历复制next random无法做到；
// Node* cur =head;
// Node* dum= new Node(0),pre =dum;
// while(cur!=nullptr){
// Node node=new Node(cur->val);
// pre->next=node;
// cur=cur->next;
// pre=node;
// }
// return dum->next;
// }
// };

0 赞同 0 条回复

mpweixin用户普通 2023年8月18日下午9:59

//先复制节点，再将各个节点的random重新分配指向。
//时间复杂度为o(n)
//空间复杂度为o(1)
class Solution {
public:
Node* copyRandomList(Node* head) {

    if(head==NULL)return NULL;
    Node *cur=head;

    while(cur){
        Node *tmp=new Node(cur->val);
        tmp->next=cur->next;
        cur->next=tmp;
        cur=tmp->next;
    }
    cur=head;
    while(cur){
        if(cur->random!=NULL)
            cur->next->random=cur->random->next;
        cur=cur->next->next;
    }
    cur=head->next;
    Node *pre=head,*res=head->next;
    while(cur->next){
        pre->next=pre->next->next;
        cur->next=cur->next->next;
        pre=pre->next;
        cur=cur->next;
    }
    pre->next=NULL;
    return res;

}

};

0 赞同 0 条回复

Delete隐身普通 2023年8月18日下午9:49

思路：使用复制 + 拆分：复制就是指原链表的每个节点的都构建出一个指相同的节点，新节点放在原节点的后面，然后遍历链表的原节点，使cur.next.random 指向 cur.random.next，拆分时记录当前节点的next节点，使当前节点的next指向当前的next的next，直到cur.next为空时停止
时间复杂度：O(n)，空间复杂度：O(n)
class Solution {
public Node copyRandomList(Node head) {
if(head null) {
return head;
}
// 复制节点
Node cur = head;
while(cur != null) {
Node newNode = new Node(cur.val);
newNode.next = cur.next;
cur.next = newNode;
cur = cur.next.next;
}
// 遍历链表的原节点，使cur.next.random 指向 cur.random.next
cur = head;
while(cur != null) {
cur.next.random = cur.random null ? null : cur.random.next;
cur = cur.next.next;
}
// 拆分链表成两个链表
cur = head;
Node newHead = cur.next;
Node curNext = null;
while(cur.next != null) {
curNext = cur.next;
cur.next = cur.next.next;
cur = curNext;
}
return newHead;
}
}

0 赞同 0 条回复

海浪漂哇漂普通 2023年8月17日下午9:24

复制链表，复制random，拆分链表
class Solution {
public Node copyRandomList(Node head) {
if(head null){
return null;
}
Node cur = head;
while(cur != null){
Node next = cur.next;
cur.next = new Node(cur.val);
cur.next.next = next;
cur = next;
}
cur = head;
while(cur != null){
Node curNew = cur.next;
curNew.random = cur.random null ? null : cur.random.next;
cur = cur.next.next;
}

    Node headNew = head.next;
    cur = head;
    Node curNew = head.next;
    while(cur != null){
        cur.next = cur.next.next;
        cur = cur.next;
        curNew.next = cur == null ? null : cur.next;
        curNew = curNew.next;
    }
    return headNew;
}

}

0 赞同 0 条回复

天亮之前普通 2023年8月17日上午7:23

/*
打卡
// Definition for a Node.
class Node {
int val;
Node next;
Node random;

public Node(int val) {
    this.val = val;
    this.next = null;
    this.random = null;
}

}
*/
class Solution {
public Node copyRandomList(Node head) {
if(head null){
return null;
}
// 复制链表节点
Node cur = head;
while(cur != null){
Node next = cur.next;
cur.next = new Node(cur.val);
cur.next.next = next;
cur = next;
}

    // 复制随机节点
    cur = head;
    while(cur != null){
        Node curNew = cur.next;
        curNew.random = cur.random == null ? null : cur.random.next;
        cur = cur.next.next;
    }

    // 拆分
    Node headNew = head.next;
    cur = head;
    Node curNew = head.next;
    while(cur != null){
        cur.next = cur.next.next;
        cur = cur.next;
        curNew.next = cur == null ? null : cur.next;
        curNew = curNew.next;
    }

    return headNew;
}

}

0 赞同 0 条回复

mpweixin用户普通 2023年8月16日下午10:34

打卡

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head == NULL) return NULL;
        //复制链表节点
        Node *cur = head;
        while(cur != NULL){
            Node *next = cur->next;//保留原始的next指针
            cur->next = new Node(cur->val);
            cur->next->next = next;

            //复制下一个原始节点
            cur = next;
        }

        //复制random指针
        cur = head;
        while(cur != NULL){
            Node *curNew = cur->next;
            //如果当前节点的random指针不为空，当前节点的复制节点的random指针指向对应的当前节点的random指针的复制节点
            curNew->random = cur->random ? cur->random->next : NULL;

            cur = cur->next->next;//跳到下一个原始节点
        }

//拆分，此时复制节点不仅有了普通的指针，还有random指针了 比如把 A->A1->B->B1->C->C1拆分成 A->B->C和A1->B1->C1
        Node * headNew = head->next;
        cur = head;
        Node * curNew = head->next;
        while(cur != NULL){
            cur->next = cur->next->next;//当前原始节点的下一个原始节点
            cur = cur->next;//跳到下一个原始节点
            //如果原始节点的next 也就是cur 不为空，复制节点的next应该是原始节点的next 也就是cur 的next，
            curNew->next = cur ? cur->next : NULL;
            curNew = curNew->next;//跳到下一个复制节点
        }
        return headNew;

    }
};

0 赞同 0 条回复

💮黧大王.exe 普通 2023年8月16日下午6:52

先复制再拆分：
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;

Node(int _val) {
    val = _val;
    next = NULL;
    random = NULL;
}

};
/
class Solution {
public:
Node copyRandomList(Node* head) {
if(headNULL){
return NULL;
}
Node *cur=head;
while(cur!=NULL){
Node *copy=new Node(cur->val);
copy->next=cur->next;
cur->next=copy;
cur=cur->next->next;
}
cur=head;
while(cur!=NULL){
if(cur->random!=NULL)
cur->next->random=cur->random->next;
cur=cur->next->next;
}
cur=head;
Node *copyHead = head->next;
Node *curCopy = head->next;
while (cur != NULL) {
cur->next = cur->next->next;
cur = cur->next;
if (curCopy->next != NULL) {
curCopy->next = curCopy->next->next;
curCopy = curCopy->next;
}
}
return copyHead;
//return cur;
}
};

0 赞同 0 条回复

一个人的风海吹了两遍普通 2023年8月16日下午4:22

看完思路可以自己写出来
没理解：
curNew.random = cur.random null ? null : cur.random.next;
curNew.next = cur null ? null : cur.next;
为什么会有null
时间复杂度O（n）
空间复杂度O（n）

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head){
        if(head == null)
            return null;
        //复制新节点
        Node cur = head;
        while(cur!=null){
            Node temp = new Node(cur.val);
            temp.next = cur.next;
            cur.next = temp;
            cur = cur.next.next;
        }

        //复制random节点
        cur = head;
        Node sep = head.next;
        while (cur!=null && sep!=null){
            sep.random = cur.random==null? null : cur.random.next;
            cur = cur.next.next;
            sep = sep.next==null? null : sep.next.next;
        }

        //拆分
        cur = head;
        sep = head.next;
        Node sep1 = head.next;
        while (cur!=null && sep1!=null){
            cur.next = cur.next.next;
            cur = cur.next;
            sep1.next = sep1.next==null? null : sep1.next.next;
            sep1 = sep1.next;
        }
        return sep;
    }
}

0 赞同 0 条回复

Miracle· 普通 2023年8月16日下午4:02

时间复杂度：o(n),空间复杂度o(n)
思路：使用一个哈希表来存储新的节点是否创建，未创建的换创建这个节点并存入哈希表中，一直递归知道head为nullptr
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;

Node(int _val) {
    val = _val;
    next = NULL;
    random = NULL;
}

};
/
class Solution {
public:
unordered_map<Node, Node*> Nodecache;

Node* copyRandomList(Node* head) {
    if (head == nullptr) return nullptr;
    if (! Nodecache.count(head)) {
        Node *newhead = new Node(head->val);
        Nodecache[head] = newhead;
        newhead->next = copyRandomList(head->next);
        newhead->random = copyRandomList(head->random); 
    }
    return Nodecache[head];
}

};

0 赞同 0 条回复

mpweixin用户永久会员 2023年8月15日下午10:05

Node* copyRandomList(Node* head) {
if(headnullptr) return nullptr;
Node* dummy = new Node(0);
dummy->next = nullptr;
dummy->random = nullptr;

    Node* cur = head;
    Node* tail = dummy;

    // 建立 原节点 与 复制节点 之间的连接
    unordered_map<Node*, Node*> originalToCopy;
    // 完成next的连接并建立映射关系
    while(cur){
        Node* p = new Node(cur->val);
        tail->next = p;
        tail = tail->next;
        p->next = nullptr;
        originalToCopy[cur] = p;

        cur = cur->next;
    }
    // cur指向原链表，current指向复制的链表
    cur = head;
    Node* current = dummy->next;
    while(cur){
        if(cur->random){
            current->random = originalToCopy[cur->random];
        }
        cur = cur->next;
        current = current->next;
    }
    return dummy->next;
}

0 赞同 0 条回复

Marc 普通 2023年8月15日下午7:24

class Solution:
    cache = dict()
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return None 
        if head not in self.cache:
            self.cache[head] = Node(head.val) 
            self.cache[head].next = self.copyRandomList(head.next)
            self.cache[head].random = self.copyRandomList(head.random)
        return self.cache[head]
时间On 空间On

0 赞同 0 条回复

mpweixin用户普通 2023年8月15日上午11:22

時間複雜度: O(n) 空間複雜度 O(n)
核心思路是遍歷兩次原始鏈表，第一次創建新節點並建立原始節點到新節點的映射(這邊使用哈希表來儲存)，第二次處理 random 指針的關係並設置新節點的 random 指針。這樣可以在保持線性時間複雜度的同時完成複製。


class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == NULL) {
            return NULL;
        }

        // use hash table to store the mapping of copied node and original node 
        unordered_map hash_map;
        Node* newHead = new Node(head->val);
        Node* temp_ptr = head->next;
        Node* new_temp = newHead;
        hash_map[head] = newHead;

        // first copy the "next" part
        while (temp_ptr != NULL) {
            new_temp->next = new Node(temp_ptr->val);
            hash_map[temp_ptr] = new_temp->next;
            temp_ptr = temp_ptr->next;
            new_temp = new_temp->next;
        }

        // second copy the "random" part
        new_temp = newHead;
        temp_ptr = head;
        while (new_temp != NULL) {
            new_temp->random = hash_map[temp_ptr->random];
            new_temp = new_temp->next;
            temp_ptr = temp_ptr->next;
        }
        return newHead;
    }
};

0 赞同 0 条回复

行动派小彩笔普通 2023年8月15日上午9:18

// 拼接和拆分，时间O(n),空间O(1)
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head) return head;
        Node* cur = head;
        while(cur)
        {
            Node* next = cur->next;
            cur->next = new Node(cur->val);
            cur->next->next = next;
            cur = next;
        }
        cur = head;
        while(cur)
        {
            if(cur->random)
                cur->next->random = cur->random->next;
            cur = cur->next->next;
        }
        cur = head;
        Node* newHead = head->next;
        Node* newCur = newHead;
        while(cur)
        {
            cur->next = cur->next->next;
            cur = cur->next;
            newCur->next = cur?cur->next:NULL;
            newCur = newCur->next;
        }
        return newHead;
    }
};

// 哈希表，时间O(n),空间O(n)
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head) return head;
        unordered_map<Node*,Node*> m;
        Node* cur = head;
        while(cur)
        {
            m[cur] = new Node(cur->val);
            cur = cur->next;
        }
        cur = head;
        while(cur)
        {
            m[cur]->next = m[cur->next];
            m[cur]->random = m[cur->random];
            cur = cur->next;
        }
        return m[head];
    }
};

0 赞同 0 条回复

小肸永久会员 2023年8月15日上午6:49

class Solution {
    /**
    步骤1: 对于每一个原来节点node，拷贝一个新节点newNode。newNode的值和原来节点的值一样，newNode.next指向node.next，node.next指向newNode.next。
    步骤2: 给每一个newNode的random指针赋值。newNode.random = (node.random == null ? null : node.random.next)。
    步骤3: 将所有newNode拆分出来，组成一个新链表返回头节点。
    注意点: 三个步骤必须分别遍历三次。
     */
    public Node copyRandomList(Node head) {
        Node doubleHead = doubleRandomList(head);
        // Node dummyHead = new Node(-1);
        // Node cur = dummyHead;
        Node cur = doubleHead;
        while (cur != null) {
            Node tmp = cur.next;
            tmp.random = (cur.random == null ? null : cur.random.next);
            // cur.next = tmp;
            // cur = cur.next;
            // doubleHead.next = doubleHead.next.next;
            // tmp.next = null;
            cur = tmp.next;
        }
        Node dummyHead = new Node(-1);
        Node resCur = dummyHead;
        Node resPre = doubleHead;
        while (resPre != null) {
            Node tmp = resPre.next;
            resCur.next = tmp;
            resCur = resCur.next;
            resPre.next = resPre.next.next;
            resPre = resPre.next;
            tmp.next = null;
        }
        return dummyHead.next;
    }
    private Node doubleRandomList(Node head) {
        Node cur = head;
        while (cur != null) {
            Node tmp = new Node(cur.val);
            tmp.next = cur.next;
            cur.next = tmp;
            cur = tmp.next;
        }
        return head;
    }
}

0 赞同 0 条回复

sincere 普通 2023年8月14日下午9:46

思路：没看懂题目。。。输入和输出一样，我还以为直接 return head，运行提示不能直接引用original one。看题解意思要深拷贝，初次遍历用 map 存储当前节点和它原始值节点的映射，再遍历将它的 next 和 random 关系赋给原始值节点，得到完整的拷贝
复杂度：时间复杂度O(n)，空间复杂度O(1)

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Map<Node, Node> map = new HashMap<>();
        Node node = head;
        // 遍历一次 复制出新节点,并创建映射
        while (node != null) {
            map.put(node, new Node(node.val));
            node = node.next;
        }
        node = head;
        while (node != null) {
            map.get(node).next = map.get(node.next);
            map.get(node).random = map.get(node.random);
            node = node.next;
        }
        return map.get(head);
    }
}

0 赞同 0 条回复

逸兴遄飞普通 2023年8月14日下午5:28

时间复杂度：O(N),
空间复杂度：O(1).

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null){
            return head;
        }

        // 复制链表节点，需要创建一个新的空白链表
        Node cur = head;
        while(cur != null){
            Node next = cur.next;
            cur.next = new Node(cur.val);
            cur.next.next = next;
            cur = next;
        }

        // 复制随机节点
        cur = head;
        while(cur != null){
            Node curnew = cur.next;
            curnew.random = cur.random == null ? null : cur.random.next;
            cur = cur.next.next;
        }

        // 将复制出的节点进行拆分
        Node headnew = head.next;
        cur = head;
        Node curnew = head.next;
        while(cur != null){
            cur.next = cur.next.next;
            cur = cur.next;
            curnew.next = cur == null ? null : cur.next;
            curnew = curnew.next;
        }

        return headnew;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年8月14日下午2:29

时间复杂度：O(N), 空间复杂度：O(N)
复制链表需要创造新的空白链表

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null){
            return head;
        }
        Node cur =head;
        while(cur!=null){
            Node temp1 = new Node(cur.val);
            temp1.next = cur.next;
            cur.next = temp1;
            cur = temp1.next;
        }
        cur = head;
        while(cur!=null){
            cur.next.random = cur.random == null ? null : cur.random.next; 
            cur = cur.next.next;
        }
        Node newhead = head.next;
        Node cur1 =head.next;
        cur = head;
        while(cur != null){
            cur.next = cur.next.next;
            cur = cur.next;
            cur1.next = cur == null? null:cur.next;
            cur1 = cur1.next;
        }
        return newhead;
    }
}

0 赞同 0 条回复

晓宇普通 2023年8月14日下午12:04

class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        if head == None:
            return None
        copyhead = Node(0)
        copycur = copyhead
        cur = head
        while cur:
            copycur.next = Node(cur.val)
            cur = cur.next
            copycur =copycur.next
        cur = head
        copycur = copyhead.next 

        while cur:
            randomcur = cur.random
            tmpcur = head
            tmpcopycur = copyhead.next

            while tmpcur:
                if randomcur == tmpcur:
                    copycur.random = tmpcopycur
                tmpcur = tmpcur.next
                tmpcopycur = tmpcopycur.next

            copycur = copycur.next
            cur = cur.next
        return copyhead.next

空间复杂度 O(N)
时间复杂度O（N2）
本题是主要是三个关键问题：
1.如何获得Random指针的元素地址

while tmpcur:
                if randomcur == tmpcur:
                    copycur.random = tmpcopycur
                tmpcur = tmpcur.next
                tmpcopycur = tmpcopycur.next

遇到类似问题可以先把这个代码写完
2、因为random是随机的，则需要遍历两遍链表，第一次只是复制全链表，不管random的值，第二次则是真复制random
3、第三个关键则为复制节点，由于复制节点，要考虑连接关系，所以我采用了虚拟头结点，来保持next的连接关系。否则的话则需要保持prev节点

0 赞同 0 条回复

JustRtn 普通 2023年8月14日上午1:50

1.不管random复制整个链表，使用map存储原链表的每个node地址对应新链表的node地址；
2.遍历链表，依据map填充新链表的random
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;

Node(int _val) {
    val = _val;
    next = NULL;
    random = NULL;
}

};
/
class Solution {
public:
Node copyRandomList(Node* head) {
if (head nullptr) {
return nullptr;
}
map<Node*, Node*> m;
Node *tmp = new Node(head->val);
Node *p = head->next;
Node *q = tmp;
m[head] = q;
while (p != nullptr) {
q->next = new Node(p->val);
m[p] = q->next;
p = p->next;
q = q->next;
}
q = tmp;
p = head;
while (q != nullptr) {
q->random = m[p->random];
p = p->next;
q = q->next;
}
return tmp;
}
};

0 赞同 0 条回复

别扒拉我普通 2023年8月13日下午11:55

1、哈希表

import java.util.*;
/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        if(pHead == null){
            return pHead;
        }
        RandomListNode res = new RandomListNode(0);
        Map<RandomListNode, RandomListNode> mp = new HashMap<>();
        RandomListNode cur = pHead;
        RandomListNode pre = res;
        while(cur != null){
            RandomListNode clone = new RandomListNode(cur.label);
            mp.put(cur, clone);
            pre.next = clone;
            pre = pre.next;
            cur = cur.next;
        }
        pre = res.next;
        while(pHead != null){
            if(pHead.random != null){
                pre.random = mp.get(pHead.random);
            }
            pre = pre.next;
            pHead = pHead.next;
        }
        return res.next;
    }
}

0 赞同 0 条回复

天亮说晚安普通 2023年8月13日下午11:21

这个题没做出来

0 赞同 0 条回复

木子有点甜🍒 普通 2023年8月13日下午10:25

“`python
本题的核心问题在于，复制。原始的单链表复制起来简单，本题的复制问题在于节点的random不好复制，因为random无法在遍历的时候按照某个规则确定指向。因此，我们遵循最原始的复制逻辑，复制结点之后，把这个复制的新节点的random改成和原节点一样的就可以了。
“””

Definition for a Node.

class Node:
def init(self, x: int, next: ‘Node’ = None, random: ‘Node’ = None):
self.val = int(x)
self.next = next
self.random = random
“””
class Solution:
def copyRandomList(self, head: ‘Node’) -> ‘Node’:
if not head: return
cur = head
#把原链表的每个节点在原链表中复制一份，复制的节点属于原节点的next
while cur:
tmp = Node(cur.val)
tmp.next = cur.next
cur.next = tmp
cur = cur.next

    #把复制的节点的random指向改变
    cur = head
    while cur:
        if cur.random:
            cur.next.random = cur.random
        cur = cur.next

    #把复制的链表拆出来
    cur = res = head.next
    pre = head

    while cur.next:
        pre.next = pre.next.next
        cur.next = cur.next.next
        pre = pre.next
        cur = cur.next

    pre.next = None
    return res

0 赞同 0 条回复

c 普通 2023年8月13日下午5:19

时间O(n)空间O(1)

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return head;
        }
        Node node = head;
        while(node!=null){
            Node copyNode = new Node(node.val);
            copyNode.next = node.next;
            node.next = copyNode;
            node=node.next.next;
        }
        node = head;
        while(node!=null){
            if(node.random!=null){
                node.next.random = node.random.next;
            }else{
                node.next.random = null;
            }

            node=node.next.next;
        }
        node = head;
        Node node1 = head.next;
        Node res = head.next;
        while(node!=null && node1!=null){
            if (node1.next!=null){
                node.next=node.next.next;
                node1.next = node1.next.next;
                node=node.next;
                node1=node1.next;
            }else{
                node.next=node.next.next;
                node1.next = null;
                node=node.next;
                node1=node1.next;
            }
        }
        return res;
    }
}

0 赞同 0 条回复

Jou Siankwa 普通 2023年8月13日下午4:02

采用哈希表Map，将原节点和新节点放入Map中，第二次遍历原链表，根据原链表的节点访问到新链表节点，访问到Map中next节点及random节点连接起来。

class Solution {
    public Node copyRandomList(Node head) {
        HashMap<Node,Node> map = new HashMap<>();
        if(head == null){
            return null;
        }
        Node cur = head;
        while (cur != null){
            map.put(cur,new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        while (cur != null){
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);

    }

    public static void main(String[] args) {
        Node a1 = new Node(7);
        Node a2 = new Node(13);
        Node a3 = new Node(11);
        Node a4 = new Node(10);
        Node a5 = new Node(1);

        a1.next = a2;
        a2.next = a3;
        a3.next = a4;
        a4.next = a5;

        a2.random = a1;
        a3.random = a5;
        a4.random = a3;
        a5.random = a1;

        Solution sol = new Solution();
        Node node = sol.copyRandomList(a1);

        while (node != null){
            System.out.println(node.random == null ? null : node.random.val);
            node = node.next;
        }

    }
}

0 赞同 0 条回复

mpweixin用户永久会员 2023年8月13日下午3:16

暴力法
时间复杂度O(n2)空间复杂度O(1)

class Solution {
    public Node copyRandomList(Node head) {
        if (head  null) {
            return null;
        }
        Node copy = new Node(-1), p = head, q = copy;
        //先把常规的next复制出来
        while (p != null) {
            Node temp = new Node (p.val);
            q.next = temp;
            p = p.next;
            q = q.next;
        }
        //复制random
        p = head;
        q = copy.next;
        while (p != null) {
            copyRandom (p, q, head, copy);
            p = p.next;
            q = q.next;
        }
        return copy.next;
    }
    public void copyRandom(Node p, Node q, Node head, Node copy) {
        if (p.random  null) {
            q.random = null;
            return ;
        }
        int i = 0;
        while (head != p.random) {
            head = head.next;
            i++;
        }
        while (i >= 0) {
            copy = copy.next;
            i--;
        }
        q.random = copy;
    }
}

0 赞同 0 条回复

【链表专题】剑指 Offer 35. 复杂链表的复制

共以下 35 个回答

思路

解题方法

复杂度

时间复杂度:

空间复杂度:

Code

Definition for a Node.

# 回答此问题取消回复

【链表专题】剑指 Offer 35. 复杂链表的复制

共以下 35 个回答

思路

解题方法

复杂度

时间复杂度:

空间复杂度:

Code

Definition for a Node.

# 回答此问题 取消回复

# 回答此问题取消回复