【链表专题】剑指 Offer 35. 复杂链表的复制-跟着帅地玩副业，开拓第二曲线PlayOffer

G 永久会员 2025年4月22日下午8:36

“`java 在每一个节点的后面复制一个值一样的节点
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;
    }

    // 拆分,比如把 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;
        curNew.next = cur == null ? null : cur.next;
        curNew = curNew.next;
    }

    return headNew;
}

}

“`
时间复杂度O(N),额外空间复杂度为O(1)

0 赞同 0 条回复

Yui 永久会员 2025年4月22日下午7:05

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;
    }
}

解题思路：本题主要使用复制拆分思想，先将原链表每个结点后面复制一个新节点，再在这个新链表中表示新节点的新random指针，最后将其拆成原链表和新链表，难点在与如何写好复制和拆分的操作。
时间复杂度：O(n)，空间复杂度：O(1)

0 赞同 0 条回复

重明鸟永久会员 2025年4月22日下午6:54

用Map集合做的，时间和空间都是和O(n)

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

0 赞同 1 条回复

重明鸟永久会员 @ 重明鸟 2025年4月22日下午7:31

学到了，还能拆分链表

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) {return null;}
        Node cur = head;
        while(cur != null) {
            Node node = new Node(cur.val);
            node.next = cur.next;
            cur.next = node;
            cur = node.next;
        }
        cur = head;
        while(cur != null) {
            cur.next.random = cur.random != null ? cur.random.next : null;
            cur = cur.next.next;
        }
        Node newHead = head.next;
        cur = head;
        Node newCur = newHead;
        while(newCur.next != null) {
            // 错误做法：在拆封时赋值random，因为random可能会指向已经拆封好的节点
            // newCur.random = cur.random != null ? cur.random.next : null;
            cur.next = cur.next.next;
            newCur.next = newCur.next.next;
            cur = cur.next;
            newCur = newCur.next;
        }
        cur.next = null;
        return newHead;
    }
}

Aatorx 永久会员 2025年4月22日下午3:57

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head) return NULL;
        Node* cur = head;
        while(cur) {
            Node* temp = new Node(cur->val);
            temp->next = cur->next;
            cur->next = temp;
            cur = cur->next->next;
        }
        cur = head;
        while(cur) {
            if(cur->random) {
                cur->next->random = cur->random->next;
            }
            cur = cur->next->next;
        }
        cur = head->next;
        Node* pre = head;
        Node* res = head->next;
        while(cur->next != NULL) {
            pre->next = pre->next->next;
            cur->next = cur->next->next;
            cur = cur->next;
            pre = pre->next;
        }
        pre->next = NULL;
        return res;
    }
};

时间复杂度O(N)，空间复杂度O(1)。

0 赞同 2 条回复

重明鸟永久会员 @ Aatorx 2025年4月22日下午6:57

空间复杂度怎么会是O（1），肯定是O（n）啊，要复制一个链表的

登录以回复
重明鸟永久会员 @ Aatorx 2025年4月22日下午7:01

哦我明白了，空间复杂度只算额外存储

登录以回复

魂牵梦萦永久会员 2025年4月22日下午2:47

看了题解才有的思路，太厉害了…惯性思维一直导致我在想怎么遍历一遍还能做到复制random，完全没想到map。

class Solution {
    Map<Node, Node> map = new HashMap<>();
    public Node copyRandomList(Node head) {
        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) {
            Node dup = map.get(cur);
            dup.next = map.get(cur.next);
            dup.random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }
}

0 赞同 0 条回复

芒种永久会员 2025年4月22日上午10:18

/*
// 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 copy = new Node(cur.val);
            copy.next = cur.next;
            cur.next = copy;
            cur = copy.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 copyCur = copyHead;
        while (cur != null) {
            cur.next = copyCur.next;
            cur = cur.next;
            if (cur != null) {
                copyCur.next = cur.next;
                copyCur = copyCur.next;
            }
        }
        return copyHead;
    }
}

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

0 赞同 0 条回复

夏目永久会员 2025年4月21日下午11:07

class Solution {
    public Node copyRandomList(Node head) {
        HashMap<Node,Node> map = new HashMap<>();
        Node virtureHead = new Node(-1);
        Node p = head,q = virtureHead;
        while(p != null){
            Node node = new Node(p.val);
            q.next = node;
            q = q.next;
            map.put(p,q);
            p = p.next;
        }
        p = head;
        q = virtureHead.next;
        while(p != null){
            q.random = map.get(p.random);
            p = p.next;
            q = q.next;
        }
        return virtureHead.next;

    }
}

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

0 赞同 0 条回复

奈何永久会员 2025年4月21日下午10:38

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

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

1 赞同 0 条回复

. 永久会员 2025年4月21日下午8:48

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

        Node cur = head;
        Node next = null;

        while (cur != null) {
            next = cur.next;
            cur.next = new Node(cur.val);
            cur.next.next = next;
            cur = next;
        }

        cur = head;

        while (cur != null) {
            next = cur.next.next;
            cur.next.random = cur.random == null ? null : cur.random.next;
            cur = next;
        }

        Node h = head.next;
        cur = head;
        while (cur != null) {
            next = cur.next.next;
            Node node = cur.next;
            cur.next = next;
            node.next = next == null ? null : next.next;
            cur = next;
        }

        return h;
    }
}

时间复杂度O(n)

空间复杂度O(1)

0 赞同 0 条回复

??? 永久会员 2025年4月21日下午7:45

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null)
            return null;
        //进行节点的复制
        Node cur = head;
        while (cur != null) {
            Node tmp = new Node(cur.val);
            tmp.next = cur.next;
            cur.next = tmp;
            cur = tmp.next;
        }
        //进行随机指向的复制
        cur = head;
        while (cur != null) {
            if (cur.random != null) {
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }
        //进行拆分
        cur = head.next;
        Node pre = head;
        Node res = head.next;
        while (cur.next != null) {

            pre.next = pre.next.next;
            cur.next = cur.next.next;
            pre = pre.next;
            cur = cur.next;
        }
        pre.next = null;
        return res;

    }
}

0 赞同 0 条回复

為愛而生普通 2025年1月2日下午3:48

时间On 空间On
class Solution {
public Node copyRandomList(Node head) {
Node cur = head;
Map<Node, Node> map = new HashMap<>();
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);
}
}

0 赞同 0 条回复

YULONG 永久会员 2024年11月30日下午2:22

/*
方法一：哈希表
第一次遍历，遍历旧链表，创建新链表，只设置next，同时建立旧新节点映射存储在哈希表
第二遍次历，同时遍历旧新两链表，添加新链表node的random值，即旧链表node的random节点在哈希表中的映射
共遍历两次，时间复杂度O(N)

*/
class Solution {

    public Node copyRandomList(Node head) {

        Map<Node,Node> m = new HashMap<>();

        Node dummy = new Node(-1);
        Node p = dummy;
        Node q = head;
        while(q != null){
            Node newNode = new Node(q.val);
            m.put(q, newNode);
            p.next = newNode;
            p = newNode;
            q = q.next;
        }

        q = head;
        p = dummy.next;
        while (q != null){
            if (q.random != null){
                p.random = m.get(q.random);
            }
            q = q.next;
            p = p.next;
        }
        return dummy.next;
    }
}

0 赞同 0 条回复

树懒在橘子洲数星星普通 2024年11月27日下午8:53

“`py
class Solution(object):
def copyRandomList(self, head):
if not head:
return
hmap={}
# 复制各个节点
cur=head
while cur:
hmap[cur]=Node(cur.val)
cur=cur.next
cur=head
# 构建新链表的next和random指向
while cur:
hmap[cur].next=hmap.get(cur.next)
hmap[cur].random=hmap.get(cur.random)
cur=cur.next
# 返回新链表的头节点
return hmap[head]
时间复杂度：O(N) 链表的长度为N
空间复杂度：O(N) 哈希表使用的额外空间

0 赞同 0 条回复

Lil Lee_ 普通 2024年11月27日下午4:04

//使用HashMap，实现
/*
// 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 cur = head;
        Map<Node, Node> map = new HashMap<>();
        //复制链表节点
        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);
    }
}

0 赞同 0 条回复

yelinliner 普通 2024年11月27日下午2:15

1、链表复制+拆分

class Solution {
    public Node copyRandomList(Node head) {
        // 非空判断
        if (head == null) {
            return null;
        }

        // 1、复制节点、即插入一个复制节点
        // 输入：A->B->C->D
        // 输出：A->A1->B->B1->C->C1->D->D1
        Node cur = head;
        while (cur != null) {
            Node temp = cur.next;// B
            cur.next = new Node(cur.val);// A链接A1
            cur.next.next = temp; // A1链接B
            // 指针从A跳到B
            cur = temp;
        }
        // 2、复制随机节点
        // A->A1->B->B1->C->C1->D->D1
        // 假设 A.random=B
        // 则 A1.random=B1
        // 即 A1.random=B.next=A.random.next
        cur = head;
        while (cur != null) {
            Node curNew = cur.next; // A1
            // A1.random=A.random.next
            curNew.random = cur.random == null ? null : cur.random.next;
            // 指针从A跳到B
            cur = cur.next.next;
        }
        // 拆分
        // 输入：A->A1->B->B1->C->C1->D->D1
        // 输出：A->B->C->D、A1->B1->C1->D1
        Node headNew = head.next;
        cur = head; // A 原链表的指针
        Node curNew = head.next; // A1 新链表的指针
        while (cur != null) {
            // A链接B
            cur.next = cur.next.next;
            // 指针跳转到B
            cur = cur.next;
            // A1链接B1
            curNew.next = cur == null ? null : cur.next;
            // 指针跳转到B1
            curNew = curNew.next;
        }
        return headNew;

    }
}

时间复杂度0(n)、空间复杂度O(1)
2、通过HashMap来实现先复制节点再指定random

0 赞同 0 条回复

陆狗陆狗普通 2024年11月26日下午10:51

题解：先复制再拆分

class Solution {
    public Node copyRandomList(Node head) {
        if(head==null){
            return null;
        }
        // 复制：A->A1->B->B1
        Node tmpt=head;
        // 【错误点1：tmpy.next!=null不可以，会导致最后一个节点不被遍历到】
        while(tmpt!=null){
            // 创建A1
            Node copy=new Node(tmpt.val);
            copy.next=tmpt.next;
            // A->B变成了A->A1
            tmpt.next=copy;
            // 移动游标
            tmpt=copy.next;
        }
        // 复制随机节点（没办法写在上面）
        tmpt=head; // 【又可以用这个从头进行遍历了】
        while(tmpt!=null){
            // A->rand,A1->rand1 ，【错误点2，有可能A->rand=null】
            tmpt.next.random=tmpt.random!=null?tmpt.random.next:null;
            // A->B(跳过A1)
            tmpt=tmpt.next.next;

        }
        // 拆分，A->B  A1->B1
        Node split=head;
        Node copyList=new Node(0);
        Node copyTempt=copyList;
        while(split!=null){
            // A1赋值给新链表
            copyTempt.next=split.next;
            // A->B,移动游标(split.next被赋值过含义就变了)
            split.next=split.next.next;
            // A1不再指向B
            copyTempt.next.next=null;
            // 移动split游标，移动copyTempt游标
            split=split.next;
            copyTempt=copyTempt.next;
        }
        return copyList.next;
    }
}

错误点1：tmpy.next!=null不可以作为条件，会导致最后一个节点不被遍历到
错误点2：有可能A->rand=null，需要进行特殊判断

0 赞同 0 条回复

岱永久会员 2024年11月26日下午9:32

用map

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        Node cur = head;
        Map<Node, Node> map = new HashMap<>();

        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);
    }
}

0 赞同 0 条回复

遇事不决睡大觉普通 2024年11月26日下午4:12

/*
// 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;
Map<Node, Node> map = new HashMap<>();
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);
}
}//主要是要记住思路

0 赞同 0 条回复

Rad 普通 2024年11月26日下午2:45

/*
// 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;



    }
}

时间复杂度On
空间复杂度O1

0 赞同 0 条回复

LovLe 普通 2024年11月24日下午5:02

哈希表

"""
# 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 head
        hmap=dict()
        cur=head
        while cur:
            hmap[cur]=Node(cur.val) #建立旧链表节点与新链表节点的映射关系，key: old Node --> value: new node 
            cur=cur.next

        cur=head
        while cur:
            hmap[cur].next=hmap.get(cur.next)   # 依次把旧链表节点的next和random赋给新链表节点；hmap[cur].next代表新链表的属性；hmap.get(cur.next)代表旧链表节点的属性
            hmap[cur].random=hmap.get(cur.random)   # 因为random指针指向的可能还没有加入到hmap中，因为cur.random 得到的是实际指向的节点，而不仅仅是cur的一个属性值

            cur=cur.next
        return hmap[head]

时间复杂度 *O*(*N*) ： 两轮遍历链表，使用 O(N) 时间。
空间复杂度 *O*(*N*) ： 哈希表 hmap 使用线性大小的额外空间。

拼接+拆分链表

拼接的好处是，旧当前节点的下一个就是新链表节点。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 None

        #1.拼接链表：隔空把新链表节点插入到旧链表的后面
        cur=head
        while cur:
            node=Node(cur.val)
            node.next=cur.next
            cur.next=node
            cur=node.next

        # 2.构建random指针，不必构建next指针，因为第一次遍历就已经按照next指针遍历，需要到最后的时候把新旧链表拆分开
        cur=head
        while cur:
            if cur.random:
                cur.next.random=cur.random.next  #指向的是新节点的random指针指向节点的下一个节点，才是新链表的random指针指向的节点
            cur=cur.next.next   #依次跳跃一个节点，到下一个旧节点遍历

        #3. 拆分链表
        cur=newhead=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 newhead

时间复杂度 *O*(*3*N*) ： 三轮遍历链表，使用 O(N) 时间。
空间复杂度 *O*(*2*N*) ： 哈希表 hmap 使用线性大小的额外空间。

0 赞同 0 条回复

张君雅小妹妹普通 2024年11月24日下午3:31

解决各种空指针花了好久

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        // 复制next
        Node cur = head;
        Node tmp;
        while(cur != null){
            tmp = cur.next; // 放在循环里的第一个，而不是最后
            Node cur_copy = new Node(cur.val);
            cur.next = cur_copy;
            cur_copy.next = tmp;
            cur = cur_copy.next;
        }

        // 复制random
        cur = head;
        while (cur != null){
            if(cur.random != null){ // 要注意cur.random为null的情况
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }

        // 拆开
        cur = head;
        Node headNew = cur.next;
        Node curNew = headNew;
        while(cur != null){
            tmp = cur.next.next;
            cur.next = tmp;
            curNew.next = tmp == null ? null : tmp.next; // 非空判断
            cur = cur.next;
            curNew = curNew.next;
        }

        return headNew;

    }
}

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

0 赞同 0 条回复

无言永久会员 2024年11月24日下午1:45

/*
// 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;
        unordered_map<Node*, Node*> m;
        Node* temp = head;
        while(temp) {
            // 复制原节点，建立"原节点->新节点"的map的映射
            Node* node = new Node(temp->val);
            m[temp] = node;
            temp = temp->next;
        }
        temp = head;
        while(temp) {
            // 新节点的next的节点 是 原节点的next的复制节点, random同理
            m[temp]->next = m[temp->next];
            m[temp]->random = m[temp->random];
            temp = temp->next;
        }
        return m[head];
    }
};
时间复杂度: O(n) 
空间复杂度: O(n)

0 赞同 0 条回复

🍊 普通 2024年11月23日下午6:22

哈希表
/*
// 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) {
Node cur = head;
Map<Node, Node> map = new HashMap<>();
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);
}
}

0 赞同 0 条回复

Pendulumpal 普通 2024年11月23日下午1:09

用哈希表记录原节点到新节点之间的映射
O(n),O(n)

“`c++
Node* copyRandomList(Node* head) {
unordered_mapmp;
Node* p=head;
while(p){
mp[p]=new Node(p->val);
p=p->next;
}
p=head;
while(p){
mp[p]->next=mp[p->next];
mp[p]->random=mp[p->random];
p=p->next;
}
return mp[head];
}
“`

0 赞同 0 条回复

Firefly 普通 2024年11月23日上午10:58

/*
// 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) {
std::unordered_map<Node,Node> mp;
for(auto p=head;p!=nullptr;p=p->next)
{
mp[p]=new Node(p->val);
}

    for(auto& item:mp)
    {
        auto first=item.first;
        auto sec=item.second;
        if(first->next!=nullptr)
            sec->next=mp[first->next];
        if(first->random!=nullptr)
            sec->random= mp[first->random];
    }
  return mp.size()>0?mp[head]:nullptr;
}

};
空间复杂度O(n)

0 赞同 0 条回复

越努力越幸运普通 2024年11月23日上午1:07

“`c++
class Solution {
public:
Node* copyRandomList(Node* head) {
if (!head) {
return nullptr;
}
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) {
        Node* curNew = cur->next;
        curNew->random = cur->random ? cur->random->next : nullptr;
        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 : nullptr;
        curNew = curNew->next;
    }

    return headNew;
}

};
//复制+拆分

“`

0 赞同 0 条回复

Poetry and distance 永久会员 2024年11月23日上午12:26

思路：只有为空链表才直接返回，一个以上都要进行复杂操作而不能直接返回，首先进行双倍复制，其次，连接random 节点，接着将双倍复制和连接好的random节点进行拆分，注意：拆分后原来链表要保持原来的样子，因此要衔接好
/*
// 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 cur=head;
        while(cur!=null){
            Node temp=cur.next;
            Node newNode=new Node(cur.val);
            cur.next=newNode;
            cur.next.next=temp;
            cur=temp;
        }
        cur=head;
        while(cur!=null){
            Node newNode=cur.next;
            newNode.random=cur.random==null?null:cur.random.next;
            cur=cur.next.next;
        }

        cur=head;
        Node res=head.next;
        Node temp=res;
        while(cur!=null){
            cur.next=cur.next.next;
            cur=cur.next;
            temp.next=cur==null?null:cur.next;
            temp=temp.next;
        }
        return res;
    }
}
时间复杂度：O(n)
空间复杂度:O（1）

0 赞同 0 条回复

Kisara 普通 2024年11月22日下午11:51

“`java
利用map构建源节点和新节点的映射关系,这样就可以迅速复制链表

/*
// 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(headnull) return null;
Node cur=head;
//建立原节点-新节点的映射关系
Map<Node,Node> map=new HashMap<>();
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);
}
}

0 赞同 0 条回复

黑键〰普通 2024年11月22日下午6:40

/**
 * // Definition for a Node.
 * function Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */

/**
 * @param {Node} head
 * @return {Node}
 */
var copyRandomList = function(head) {
    if(head == null) return head
    // copy new node
    let p0 = head
    while(p0 != null) {
        let nxt = p0.next
        let newP0 = new Node(p0.val) // copy cur node's value
        p0.next = newP0 // change next direction
        p0.next.next = nxt == null ? null : nxt // new node links to next node
        p0 = nxt // move cur node
    }

    // copy random points
    let cur = head
    while(cur != null) {
        let nxtr = cur.next.next
        let newcur = cur.next
        newcur.random = cur.random == null ? null : cur.random.next
        cur = nxtr
    }

    // split new linklist and old list
    let newHead = head.next
    // two points towards two list's headnode
    cur = head
    let newcur = head.next
    while(cur != null) {
        cur.next = cur.next.next
        cur = cur.next
        newcur.next = cur == null ? null : cur.next
        newcur = newcur.next
    }
    return newHead
};

看视频学了一遍，自己画了图理清了思路，然后过了一个小时自己重新写了一遍
思路没问题，暂时可以说理解了，还是会有一些细节点的地方会写错
anyway，任何时候可以先判断一下头结点是不是就为null，先把这个if写出来

0 赞同 0 条回复

Renasc 普通 2024年11月22日下午3:34

时间复杂度O(n)，空间复杂度O(n)

class Solution {
    public Node copyRandomList(Node head) {
        // 如果是空节点，直接返回
        if (head == null) {
            return head;
        }

        // 通过HashMap的key来保存原节点，value来保存新节点
        Map<Node, Node> map = new HashMap<>();

        // 先复制节点
        Node curr = head;
        while (curr != null) {
            map.put(curr, new Node(curr.val));
            curr = curr.next;
        }

        // 再复制指向
        curr = head;
        while (curr != null) {
            map.get(curr).next = map.get(curr.next);
            map.get(curr).random = map.get(curr.random);
            curr = curr.next;
        }

        // 返回复制后的头结点
        return map.get(head);
    }
}

0 赞同 0 条回复

zing 普通 2024年11月22日下午1:38

不知道这个解法和递归的关系

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head: return
        hmap = {}
        # 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
        cur = head
        while cur:
            hmap[cur] = Node(cur.val)
            cur = cur.next
        cur = head
        # 4. 构建新节点的 next 和 random 指向
        while cur:
            hmap[cur].next = hmap.get(cur.next)
            hmap[cur].random = hmap.get(cur.random)
            cur = cur.next
        # 5. 返回新链表的头节点
        return hmap[head]

0 赞同 0 条回复

youngsir 普通 2024年11月22日上午9:45

class Solution {
public:
Node* copyRandomList(Node* head) {
if(head nullptr){
return nullptr;
}
Node* cur = head;
while(cur!=nullptr){
Node* temp = new Node(cur->val);
temp->next = cur->next;
cur->next = temp;
cur = temp->next;
}

    cur = head;
    while(cur!=nullptr){
        if(cur->random!=nullptr){
            cur->next->random = cur->random->next;
        }
        cur = cur->next->next;
    }

    cur = head->next;
    Node* pre = head,*res = head->next;
    while(cur->next!=nullptr){
        pre->next = pre->next->next;
        cur->next = cur->next->next;
        pre = pre->next;
        cur = cur->next;
    }
    pre->next = nullptr;
    return res;



}

};
时间复杂度O（n），空间复杂度O（n）

0 赞同 0 条回复

Xiang. 永久会员 2024年11月22日上午9:41

class Solution {
public Node copyRandomList(Node head) {
Map<Node,Node> tmp=new HashMap<>(); //借用hashmap，将父子结点作为键值对存入到到mapNode中，利用这一绑定关系实现next的传递
Node cur=head;
while(cur!=null){
tmp.put(cur,new Node(cur.val));
cur=cur.next;
}
cur=head;
while(cur!=null){
tmp.get(cur).next=tmp.get(cur.next);
tmp.get(cur).random=tmp.get(cur.random);
cur=cur.next;
}
return tmp.get(head);
}
}
时间复杂度 O(n)
空间复杂度 O(n)

0 赞同 0 条回复

jaron 普通 2024年11月22日上午9:35

复制再分离

时间复杂度：O(n)

额外空间复杂度：O(1)

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 = temp.next;
        }
        // 复制 random 指针
        cur = head;
        while (cur != null) {
            // 避免空指针
            if (cur.random != null) {
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }
        // 分离新旧节点
        Node newHead = head.next; // 新链表的头节点
        cur = head;
        Node copy = newHead;
        while (cur != null) {
            cur.next = cur.next.next; // 还原旧链表
            if (copy.next != null) {
                copy.next = copy.next.next; // 连接新链表
            }
            cur = cur.next;
            copy = copy.next;
        }
        return newHead;
    }
}

不能一边复制节点一边复制 random 指针，这样新节点的radom会指向旧节点
要还原原始链表

哈希表

时间复杂度：O(n)

空间复杂度：O(n)

建立新旧节点的对应关系

class Solution {
    public static HashMap<Node, Node> map = new HashMap<>();

    public Node copyRandomList(Node head) {
        if (head == null) return null;
        Node cur = head;
        while (cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        for (Node n : map.keySet()) {
            map.get(n).next = map.get(n.next);
            map.get(n).random = map.get(n.random);
        }
        // 如果还要使用head，就要搞一个cur，不然最后head就变成空了
        return map.get(head);
    }
}

0 赞同 0 条回复

Tom Yuan 普通 2024年11月22日上午8:18

先复制值，再创建链接和random部分
用hashmap来一一对应，然后再按顺序复制剩下的部分。

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head: return 
        # dict between old node and new node
        hmap = {}
        temp = head
        while temp:
            # first create the new node with the val
            hmap[temp] = Node(temp.val)
            temp = temp.next

        temp = head
        while temp:
            # re-create the links and random
            hmap[temp].next = hmap.get(temp.next)
            hmap[temp].random = hmap.get(temp.random)
            temp = temp.next

        return hmap[head]

time O(n) space O(n)
这种办法可能空间不是最优解但复制拆分感觉不如这个直白

0 赞同 0 条回复

mpweixin用户普通 2024年11月22日上午1:42

class Solution {
public:
Node* copyRandomList(Node* head) {
if(head NULL){
return head;
}
Node* p = head;
while(p){
Node* temp = p->next;
Node* q = new Node(p->val);
p->next = q;
q->next = temp;
p = temp;
}
p = head;
while(p){
Node* temp = p->next->next;
if(p->random){
p->next->random = p->random->next;
}
p = temp;
}
p = head;
Node* result = head->next;
while(p){
Node* temp = p->next->next;
if(temp){
p->next->next = temp->next;
}
p->next = temp;
p = temp;
}
return result;
}
};
思路：先复制相同值的新节点连接在原型之后，再处理random的指向，最后把原链表恢复，新链表断开提出返回。
时间复杂度O(N)，空间复杂度O(1)。

0 赞同 0 条回复

生活在经验里普通 2024年11月22日上午12:12

func copyRandomList(head *Node) *Node {
    if head == nil {
        return nil
    }

    m := make(map[*Node]*Node)
    // 创建新节点, 并建立 原节点 到 新节点 的映射
    // 第1次循环不能赋值next和random：否则指向的是原链表节点
    for cur := head; cur != nil; cur = cur.Next {
        newNode := &Node{
            Val: cur.Val,
        }
        m[cur] = newNode
    }

    // 第2次循环赋值next和random: 此时新链表节点已经创建好
    for cur := head; cur != nil; cur = cur.Next {
        m[cur].Next = m[cur.Next]
        m[cur].Random = m[cur.Random]
    }
    return m[head]
}

0 赞同 0 条回复

momo 普通 2024年11月21日下午11:46

class Solution:
def copyRandomList(self, head: ‘Optional[Node]’) -> ‘Optional[Node]’:
if head None:
return None

    cur = head
    while cur:
        cur.next = Node(cur.val, cur.next)
        cur = cur.next.next

    cur = head
    while cur:
        if cur.random:
            cur.next.random = cur.random.next
        cur = cur.next.next 

    cur = head.next
    while(cur.next):
        cur.next = cur.next.next
        cur = cur.next

    return head.next

思路：在每个节点后复制原链表，再删除原来的

0 赞同 0 条回复

parsons 普通 2024年11月21日下午10:00

class Solution {
public:
Node* copyRandomList(Node* head) {
//1.如果链表是空链表，直接返回
if(head nullptr)
return nullptr;
//2.创建哈希表，存储复制节点
unordered_map<Node*, Node> NodeMap;
//3.进行复制操作
Node cur = head;
while(cur){
NodeMap[cur] = new Node(cur->val);
cur = cur->next;
}
//4.进行random指针和next指针的转移
cur = head;
while(cur){
NodeMap[cur]->next = NodeMap[cur->next];
NodeMap[cur]->random = NodeMap[cur->random];
cur = cur->next;
}
//5.返回链表头节点
return NodeMap[head];
}
};
时间o(n)
空间o(n)

0 赞同 0 条回复

月下足迹普通 2024年11月21日下午9:23

//用一个哈希表来映射原节点和新节点，遍历两次，时间复杂度为O(N),空间复杂度O(n)

if(head null) {
return head;
}

    //创建一个哈希表建立原节点和新节点的映射
    HashMap<Node, Node> map = new HashMap<>();

    //第一遍遍历：复制所有节点，并建立原节点与新节点的映射
    Node current = head;
    while(current != null) {
        map.put(current, new Node(current.val));
        current = current.next;
    }

    // 第二遍遍历：设置新节点的 next 和 random 指针
    current = head;
    while(current != null) {
        Node newNode = map.get(current);
        newNode.next = map.get(current.next);
        newNode.random = map.get(current.random);
        current = current.next;
    }

    return map.get(head);

0 赞同 0 条回复

Jerry 普通 2024年11月21日下午9:23

class Solution {
public:
    Node* copyRandomList(Node* head) {
        unordered_map<Node*, Node*> memo;
        Node* newhead = new Node(-1);
        Node* ptr_old = head;
        Node* ptr_new = newhead;
        while(ptr_old){
            Node* newnode = new Node(ptr_old->val);
            ptr_new->next = newnode;
            memo[ptr_old] = newnode;
            ptr_old = ptr_old->next;
            ptr_new = ptr_new->next;
        }
        ptr_old = head;
        ptr_new = newhead->next;
        while(ptr_old){
            if(!ptr_old->random) ptr_new->random = NULL;
            ptr_new->random = memo[ptr_old->random];

            ptr_old = ptr_old->next;
            ptr_new = ptr_new->next;
        }
        return newhead->next;
    }

};

时间o(n)
空间o(n)

0 赞同 0 条回复

mpweixin用户普通 2024年11月21日下午9:16

a.代码及其思路

class Solution {
public:
    Node* copyRandomList(Node* head) {
        unordered_map<Node*,Node*> h;
        //首先将节点单个复制到拷贝节点里面
        for(Node* cur = head;cur;cur=cur->next)
        {
            h[cur] = new Node(cur->val);
        }
        //然后将next节点和next节点在拷贝链表中进行指针的指向
        for(Node* cur = head;cur;cur= cur->next)
        {
            if(cur->next) h[cur]->next = h[cur->next];
            if(cur->random) h[cur]->random = h[cur->random];
        }
        return h[head];
    }
};

b.时间复杂度o(n)，n为链表长度；空间复杂度o(n)，哈希表需要额外n的常数空间；

0 赞同 0 条回复

迢迢星野普通 2024年11月21日下午9:11

class Solution {
    public Node copyRandomList(Node head) {
        return linkCopy(head);
    }

    // 方法二：old1 -> new1 -> old2 -> new2 -> ...；将原始节点和新链表的节点一一连接后，再进行拆分
    private Node linkCopy(Node head) {
        if (head == null) {
            return head;
        }
        Node cur = head;
        while (cur != null) {
            Node tmp = new Node(cur.val);
            tmp.next = cur.next;
            cur.next = tmp;
            cur = tmp.next;
        }

        // 对新节点的 random 进行复制
        cur = head;
        while (cur != null) {
            if (cur.random != null) {
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }

        // 拆分链表
        Node newHead = head.next;
        Node newCur = newHead;
        cur = head;
        while (newCur != null && newCur.next != null) {
            cur.next = cur.next.next;
            newCur.next = newCur.next.next;

            newCur = newCur.next;
            cur = cur.next;
        }
        cur.next = null;

        return newHead;
    }

    // 方法一：哈希表，记录原始节点 -> 新节点的映射关系
    private Node hashCopy(Node head) {
        if(head == null) {
            return head;
        }

        HashMap<Node, Node> dic = new HashMap<>();
        Node cur = head;
        while(cur != null) {
            dic.put(cur, new Node(cur.val));
            cur = cur.next;
        }

        // 更新新链表的 next、random 指针
        cur = head;
        while(cur != null) {
            dic.get(cur).next = (cur.next != null) ? dic.get(cur.next) : null;
            dic.get(cur).random = (cur.random != null) ? dic.get(cur.random) : null;
            cur = cur.next;
        }

        return dic.get(head);
    }
}

思路：① 哈希表实现复杂链表的复制；② 使用合并 + 拆分的方式实现；
① 哈希表实现复杂链表的复制：使用一个哈希表记录原链表节点与复制后链表节点之间的映射，遍历原始链表时，为每个原始节点创建一个新节点，并将其存入到哈希表中；可以根据哈希表的映射关系，查找对应的节点，对新节点的 next、random 指针进行赋值；返回 head 对应的新链表的头节点。
时间复杂度：O(n)，遍历了 2 次链表。
空间复杂度：O(n)，使用了哈希表存储映射关系。

② 合并与拆分：将原始链表节点与复制链表节点合并成一个大的链表，形式如：old1->new1->old2->new2->old3->new3->... ；利用原始节点的 random 为新节点的 random 进行赋值；最后将大链表拆分为原始链表和复制链表，注意最后需要断开原始链表最后一个节点与新链表之间的连接；返回新链表的头节点。
时间复杂度：O(n)，遍历了 3 次链表。
空间复杂度：O(1)，只使用了常数级的额外空间。

0 赞同 0 条回复

lQl 永久会员 2024年11月21日下午9:07

链表深拷贝:先构建新链表与原链表的关系,只插入数值,然后处理新链表的节点间的对应关系

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

0 赞同 0 条回复

苯庸普通 2024年11月21日下午8:56

public Node copyRandomList(Node head) {
if (head null) {
return head;
}
//将拷贝节点放到原节点后面，例如1->2->3这样的链表就变成了这样1->1′->2->2′->3->3′
for(Node cur = head, copy = null; cur != null; cur = cur.next.next){
copy = new Node(cur.val);
copy.next = cur.next;
cur.next = copy;
}
//把拷贝节点的random指针安排上
for(Node cur = head; cur != null; cur = cur.next.next){
if(cur.random != null){
cur.next.random = cur.random.next;
}
}
//分离拷贝节点和原节点1->1′->2->2′->3->3’，变成1->2->3和1′->2′->3’两个链表，后者就是答案
Node newHead = head.next;
for(Node cur = head, tmp = null; cur != null && cur.next != null;){
tmp = cur.next;
cur.next = tmp.next;
cur = tmp;
}
return newHead;
}
思路：首先复制节点接在原节点后，然后再分离
时间：O（n）
空间：O（n）

0 赞同 0 条回复

WYX 普通 2024年11月21日下午8:31

思路：使用 HashMap 建立一个 <oldNode, newNode> 。首先不连接radom，建立一个与head 相同的链表 ans，并保存当前的<oldNode, newNode> 关系。建立完 ans 后遍历一遍 ans，以连接radom。通过查询 rem.get(head.random) 可以得到当前newNode 所对应的 oldNode 的radom指向的oldNode 所对应的 newNode

class Solution {
    public Node copyRandomList(Node head) {
        Node headRem = head;


    Node ans = new Node(-1);
    Node current = ans;

    HashMap rem = new HashMap<>();

    while(head != null){
        Node temp = new Node(head.val);
        current.next = temp;
        current = temp;

        rem.put(head, temp);
        head = head.next;
    }

    current = ans.next;
    head = headRem;
    while(current != null){
        Node nextNode = rem.get(head.random);
        current.random = nextNode;

        current = current.next;
        head = head.next;
    }

    return ans.next;

}


}

0 赞同 0 条回复

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

共以下 46 个回答

时间复杂度O(n)

空间复杂度O(1)

哈希表

拼接+拆分链表

# 回答此问题取消回复

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

共以下 46 个回答

时间复杂度O(n)

空间复杂度O(1)

哈希表

拼接+拆分链表

# 回答此问题 取消回复

# 回答此问题取消回复