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

lucca 普通 2022年12月30日上午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;

    // 复制: A->B->C => A->A'->B->B'->C->C'
    Node p = head;
    while (p != null) {
        Node cur = new Node(p.val);
        cur.next = p.next;
        p.next = cur;
        p = p.next.next;
    }

    // 复制random (原链表的节点只要不为空，必然有复制版)
    p = head;
    while (p != null) {
        // 为null就为null，否则就是它的复制版
        p.next.random = (p.random == null ? null : p.random.next);
        // 一次移动两个
        p = p.next.next;
    }

    // 划分 A->A'->B->B'->C->C' => A->B->C->A'->B'->C'
    p = head;
    Node newH = head.next;
    Node newP = head.next;
    while (p != null) {
        p.next = newP.next;
        p = p.next;
        newP.next = (p == null ? null : p.next);
        newP = newP.next;
    }
    return newH;
}

}

0 赞同 0 条回复

糖鑫普通 2022年12月3日上午12:11

/*
// 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 {
    //难点在于random指针的复制，运用Map来实现
    //java集合
    public Node copyRandomList(Node head) {
        Map<Node,Node> map=new HashMap<>();
        Node cur=head;
        while(cur!=null){
            Node node=new Node(cur.val);
            map.put(cur,node);
            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 条回复

mpweixin用户普通 2022年11月21日下午4:19

class RandomListNode:
    def __init__(self, x):
        self.label = x
        self.next = None
        self.random = None

class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here
        #空节点直接返回
        if pHead is None:
            return pHead
        #添加一个头部节点
        cur = pHead
        #遍历原始链表，开始复制
        while cur is not None:
            #拷贝节点
            clone = RandomListNode(cur.label)
            #将新节点插入到被拷贝的节点后
            clone.next = cur.next       # 当前指向下一节点的指针 变成 拷贝后节点指向下一节点的指针
            cur.next = clone            # 当前指向下一节点的位置是拷贝后的节点
            cur = clone.next            # 遍历的第一个节点
        cur = pHead
        clone = pHead.next
        res = pHead.next

        #连接新链表的random节点;二次遍历
        while cur is not None:
            #跟随前一个连接random
            if cur.random is None:
                clone.random = None
                #后一个节点才是拷贝的
            else:
                clone.random = cur.random.next # 图
            #cur.next必定不为空
            cur = cur.next.next
            #检查末尾节点
            if clone.next is not None:
                clone = clone.next.next
        cur = pHead
        clone = pHead.next

        #拆分两个链表
        while cur is not None:
            #cur.next必定不为空
            cur.next = cur.next.next
            cur = cur.next
            #检查末尾节点
            if clone.next is not None:
                clone.next = clone.next.next
            clone = clone.next
        return res
时间复杂度On，第一次遍历n，第二次和第三次是2n
空间复杂度O1

0 赞同 0 条回复

PatNick 普通 2022年11月19日下午3:52

def copyRandomList(head: 'Node') -> 'Node':
    '''
    第一步：现将每个节点进行copy，并连接在当前节点后：a-b-c复制为a-a'-b-b'-c-c'
    第二步：copy原节点的random值
    第三步：拆分链表
    Args:
        head:

    Returns:

    '''
    if not head:
        return head

    cur = head

    # 第一轮copy值和next
    while cur:
        after = cur.next
        new_cur = Node(cur.val)
        cur.next = new_cur
        cur.next.next = after
        cur = after

    # 第二轮copy节点的随机数
    cur = head
    while cur:
        new = cur.next
        new.random = None if cur.random == None else cur.random.next
        cur = cur.next.next

    # 第三轮将经过复制后的链表进行拆分
    # a-a'-b-b'c-c'
    # 拆分为a-b-c，和a'-b'-c'
    cur = head
    copy_cur = head.next
    head_cur = head.next
    while cur:
        cur.next = copy_cur.next
        cur = cur.next
        # 这里注意cur为空的情况
        copy_cur.next = cur.next if cur != None else None

        copy_cur = copy_cur.next

    return head_cur

0 赞同 0 条回复

Xiao 普通 2022年11月16日下午8:56

class Solution {
    public Node copyRandomList(Node head) {
        if(head==null) return head;
        Node a=head;
        while(a!=null){// 复制各节点，并构建拼接链表
            Node b=new Node(a.val);
            b.next=a.next;
            a.next=b;
            a=a.next.next;
        }
        a=head;
        while(a!=null){ //构建各新节点的 random 指向
            if(a.random!=null){
            a.next.random=a.random.next;
            }
            a=a.next.next;
        }

        a = head.next;
        Node pre = head, res = head.next;
        while(a.next != null) {
            pre.next = pre.next.next;
            a.next = a.next.next;
            pre = pre.next;
            a = a.next;
        }
        pre.next = null; // 单独处理原链表尾节点
        return res;      // 返回新链表头节       
}
}

0 赞同 0 条回复

hmmm 普通 2022年11月1日下午10:12

“`c++
class Solution {
public:
Node* copyRandomList(Node* head) {
if(!head)
return NULL;

    // 复制链表节点 比如将A->B->C->D复制为：A->A1->B->B1->C->C1->D->D1
    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 *rand = cur->random;
        cur->next->random = rand == NULL ? NULL : rand->next;
        cur = cur->next->next;
    }

    // 拆分 比如将A->A1->B->B1->C->C1->D->D1拆分为：A->B->C->D和A1->B1->C1->D1，并将A1返回
    Node *headNew = head->next;
    cur = head;
    Node *curNew = head->next;
    while(cur)
    {
        cur->next = cur->next->next;//A->B
        cur = cur->next;
        curNew->next = cur == NULL ? NULL : cur->next;
        curNew = curNew->next;

    }
    return headNew;
}

};
”’
时间复杂度：O(n)
空间复杂度:O(1)【注意没有额外辅助空间，创建链表的空间是必须要的，不是额外的】

0 赞同 0 条回复

长青普通 2022年10月29日下午9:20

#时间复杂度o(N)
#空间复杂度o(1)

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

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;

}
}

“`java

0 赞同 1 条回复

长青普通 @ 长青 2022年10月29日下午9:32
#时间复杂度o(N)
#空间复杂度o(1)

“`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;
}
```
 Node headNew=head.next;
 cur=head;
 Node curNew=head.next;
```
while(cur!=null){
cur.next=cur.next.next;
cur=cur.next;
curNew.next=curnull? null:cur.next;
curNew=curNew.next;
}
```
return headNew;
```
}
}

“`java
登录以回复

和普通 2022年10月29日上午11:11

public Node copyRandomList(Node head) {
        //运用哈希
            Node node =head;
            HashMap<Node,Node> map = new HashMap<>();
            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 条回复

王艺超普通 2022年10月28日下午10:20

这题做了好几遍，深入理解了双链表

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

       Node *cur = head;
       while(cur != NULL)
       {
           Node *clone = new Node(cur->val);
           clone->next = cur->next;
           cur->next = clone;
           cur = clone->next;
       }

       cur = head;
       Node *clone = head->next;
       Node *cloneHead = head->next;
       while(cur != NULL)
       {
           if(cur->random == NULL)
           {
               clone->random = NULL;
           }
           else
           {
               clone->random = cur->random->next;
           }
           cur = cur->next->next;
           if(clone->next != NULL)
           {
               clone = clone->next->next;
           }
       }

       cur = head;
       clone = head->next;
       while(cur != NULL)
       {
           cur->next = cur->next->next;
           cur = cur->next;
           if(clone->next != NULL)
           {
               clone->next = clone->next->next;
           }
           clone = clone->next;
       }
       return cloneHead;
    }

};

0 赞同 0 条回复

叶页耶夜烨邺普通 2022年10月28日下午8:10

复制+拆分

/*
// 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) return nullptr;
        Node* curr = head;
        while(curr){
            Node* copy = new Node(curr->val);
            copy->next = curr->next;
            curr->next = copy;
            curr = copy->next;
        }
        curr = head;
        while(curr){
            curr->next->random = curr->random == nullptr ? nullptr : curr->random->next;
            curr = curr->next->next;
        }
        Node* headNew = head->next;
        curr = head;
        Node* currNew = head->next;
        while(curr != nullptr){
            curr->next = curr->next->next;
            curr = curr->next;
            currNew->next = curr == nullptr ? nullptr : curr->next;
            currNew = currNew->next;
        }
        return headNew;
    }

private:
    void print(Node* head){
        Node* tmp = head;
        while(tmp){
            cout << tmp->val;
            if(tmp->random){
                cout << '(' << tmp->random->val << ')';
            }else{
                cout << "(nullptr)";
            }
            cout << "->";
            tmp = tmp->next;
        }
        cout << "NULL" << endl;
    }
};

0 赞同 0 条回复

晨普通 2022年10月27日下午5:14

class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        if not head:
            cur = head
            return cur
        # 复制链表节点
        cur = head
        while cur :
            newnode = Node(cur.val)
            newnode.next = cur.next
            cur.next = newnode
            cur = newnode.next
        # 复制链表节点的随机指针
        cur = head
        while cur:
            if cur.random:
                cur.next.random = cur.random.next
            cur = cur.next.next
        #拆分链表,new代表新链表，old代表原链表
        res = head.next
        new = res
        old = head
        while new.next:
            old.next = old.next.next
            new.next = new.next.next
            old = old.next
            new = new.next
        # 单独处理原链表末尾节点
        old.next = None
        return res

0 赞同 0 条回复

cute. 普通 2022年10月27日下午3:39

解法一:哈希
①由于随机指针的存在，当拷贝节点时，当前节点的随机指向的节点可能还没创建，因此用哈希表记录每一个节点对应的新节点
②先不考虑random指针，和原本的链表复制一样，创建新节点，并构造next指针关系，同时使用哈希表记录原节点和新节点的映射关系
③对原链表和新链表进行同时遍历，对于原链表的每个节点上的random都通过哈希表找到对应的新的random节点，并在新链表上构造random关系

var copyRandomList = function(head) {
    if(!head) return head;
    let node = head;
    let map = new Map();

    // 复制节点，将新节点放入map中
    while(node){
        map.set(node, new Node(node.val));
        node = node.next;
    }
    node = head;

    //对map里的新节点进行遍历操作
    while(node){
        map.get(node).next = map.get(node.next) === undefined ? null : map. get(node.next);
        map.get(node).random = map.get(node.random);
        node = node.next;
    }
    return map.get(head);
};

● 时间复杂度:O(n)
● 空间复杂度:O(n)
解法二：复制+拆分
思路:
①在原链表每一个节点后，复制一下节点，再为每一个新节点的random属性赋值
②将当前链表，按照一个间隔一个的顺序拆分开，将新节点，串成一个新链表，将原链表的节点，拆出来并组合成原链表
③将原链表的最后一个节点的next指针，重新指向null

var copyRandomList = function(head){
    if(!head) return head;
    let node = head;

    // 复制节点，将新节点放到原节点后面
    while(node){
        node.next = new Node(node.val, node.next);
        node = node.next.next;
    }

    node = head;
    // 构建新节点的random指向
    while(node){
        if(node.random !== null)
        node.next.random = node.random.next;
        node = node.next.next;
    }

    // 拆分链表
    let newNode = head.next, res = newNode;
    node = head;
    while(node.next && newNode.next){
        node.next = node.next.next;
        newNode.next = newNode.next.next;
        node = node.next;
        newNode = newNode.next;
    }
    node.next= null;

    // 返回新链表的头结点
    return res;
}

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

0 赞同 0 条回复

如梦似歌普通 2022年10月26日下午10:29

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

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

0 赞同 0 条回复

lobort 普通 2022年10月26日下午9:50

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;   //上面cur已经遍历完在链表末尾  重置cur
        while(cur!=null){
            if(cur.random!=null){  
                cur.next.random = cur.random.next;
            }
            cur =cur.next.next;
        }

        //拆分新旧链表
         Node res =cur = head.next;  //创建双指针进行拆分
         Node pre =head;
         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 条回复

xye 普通 2022年10月26日下午1:19

func copyRandomList(head *Node) *Node {
    if head == nil {
        return nil
    }
    //复制val和Next
    for cur := head; cur != nil; cur = cur.Next.Next {
        cur.Next = &Node{Val: cur.Val, Next: cur.Next}
    }
    //
    for cur := head; cur != nil; cur = cur.Next.Next {
        if cur.Random != nil {
            cur.Next.Random = cur.Random.Next
        }
    }

    newHead := head.Next
    for curr := head; curr != nil && curr.Next != nil; {
        tmp := curr.Next
        curr.Next = curr.Next.Next
        curr = tmp
    }
    return newHead
}

迭代拆分

0 赞同 0 条回复

努力刷题普通 2022年10月26日上午6:18

class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        if not head:
            return None
        # 1. 复制节点
        cur = head
        while cur:
            copy = Node(cur.val)
            copy.next = cur.next
            cur.next = copy
            cur = copy.next
        # 2. 复制random
        cur = head
        while cur:
            if cur.random:
                cur.next.random = cur.random.next
            cur = cur.next.next

        # 3. 拆分链表
        cur = head
        new = head.next
        while cur.next:
            tmp = cur.next
            cur.next = tmp.next
            cur = tmp
        return new
时间复杂度：O(n)
空间复杂度：O(1)

0 赞同 0 条回复

symbol 普通 2022年10月25日下午9:51

func copyRandomList(head *Node) *Node {
    if head == nil {
        return nil
    }
    for node := head; node != nil; node = node.Next.Next { //创建新节点
        node.Next = &Node{Val: node.Val, Next: node.Next}
    }
    for node := head; node != nil; node = node.Next.Next { //开始对随机节点赋值
        if node.Random != nil {
            node.Next.Random = node.Random.Next
        }
    }
    //拆分链表  画图更好理解
    headNew := head.Next
    for node := head; node != nil; node = node.Next {
        nodeNew := node.Next
        node.Next = node.Next.Next
        if nodeNew.Next != nil {
            nodeNew.Next = nodeNew.Next.Next
        }
    }
    return headNew
}

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

0 赞同 0 条回复

云雾里普通 2022年10月25日下午9:03

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

0 赞同 0 条回复

Tolkien 永久会员 2022年10月25日下午8:28

方法一：原地复制拆分
1. 时间复杂度：O(n)
2. 空间复杂度：O(1)
3. 代码

public Node copyRandomList(Node head) {
        // 1. 特殊情况判断
        if (head == null) {
            return null;
        }

        // 2. 复制每个节点元素，并追加至节点之后
        Node temp = head;
        while (temp != null) {
            Node next = temp.next;
            temp.next = new Node(temp.val);
            temp.next.next = next;
            temp = next;
        }

        // 3. 新节点的random为旧节点的random的next
        temp = head;
        while (temp != null) {
            temp.next.random = temp.random == null ? null : temp.random.next;
            temp = temp.next.next;
        }

        // 4. 拆分复制后的链表得到结果（为什么不删除旧节点，因为题目要求不能修改原链表）
        Node newHead = head.next;
        Node curr = head;
        Node newCurr = head.next;
        while (curr != null) {
            curr.next = curr.next.next;
            curr = curr.next;
            newCurr.next = curr == null ? null : curr.next;
            newCurr = newCurr.next;
        }

        return newHead;
    }

0 赞同 0 条回复

星河普通 2022年10月25日下午1:06

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        Node cur = head;
        // 1. 复制各节点，并构建拼接链表
        while(cur != null) {
            Node tmp = new Node(cur.val);
            tmp.next = cur.next;
            cur.next = tmp;
            cur = tmp.next;
        }
        // 2. 构建各新节点的 random 指向
        cur = head;
        while(cur != null) {
            if(cur.random != null)
                cur.next.random = cur.random.next;
            cur = cur.next.next;
        }
        // 3. 拆分两链表
        cur = head.next;
        Node pre = head, 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;      // 返回新链表头节点
    }
}
时间O(N)，空间O(1)

0 赞同 0 条回复

马啸天永久会员 2022年10月25日上午1:26

public class Solution {
    public Node copyRandomList(Node head) {

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

        //先复制a->a`->b->b`->c->c`
        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->a`->b->b`->c->c`进行拆分
        Node headNew = head.next;
        Node curNew = head.next;
        cur = head;
        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 条回复

鸿渐普通 2022年10月24日下午10:38

    public Node copyRandomList(Node head) {
        //使用hash表的方法去解决这个问题
        if (head==null){
            return null;
        }
        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 条回复

庄重普通 2022年10月24日下午9:57

//差点没看懂题
//题意是复制一份全新的链表，这个链表和传入链表是一样的，返回全新链表的头指针
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head == NULL) return NULL;

        //进行复制链表
        //对原有节点进行复制
        Node* pCur = head;
        Node* pNew = NULL;
        Node* pTmp = NULL;
        while(pCur != NULL){
            pTmp = pCur->next;
            pNew = new Node(pCur->val);
            pCur->next = pNew;
            pNew->next = pTmp;
            pCur = pTmp;
        }
        //a->a1->b->b1->c->c1
        //复制 复制节点的random节点
        pCur = head;
        pTmp = NULL;
        while(pCur != NULL){
            pTmp = pCur->next;
            pTmp->random = pCur->random == NULL ? NULL : pCur->random->next;
            pCur = pCur->next->next;
        }

        //进行拆分,进行拆分的时候，别忘了也要还原原链表的关系
        pCur = head;
        pTmp = NULL;
        //辅助头节点
        pNew = new Node(-1);
        Node* pRet = pNew;
        while(pCur != NULL){
            pTmp = pCur->next->next;
            pNew->next = pCur->next;
            pNew = pNew->next;
            pCur->next = pTmp;
            pCur = pTmp;
        }

        return pRet->next;

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

0 赞同 0 条回复

🚲南下普通 2022年10月24日下午8:51

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

class Solution {
public:
    Node* copyRandomList(Node* head) {
        // 先复制
        if(head==nullptr){
            return nullptr;
        }
        //将A-B-C，变成A-A'-B-B'-C-C'
        Node* cur = head;
        while(cur!=nullptr){
            Node* next = cur->next; //先保存A的next节点
            cur->next = new Node(cur->val); //复制当前节点并作为cur的next节点
            cur->next->next = next; //链接cur下一个节点的指向
            cur = next;//移动当前节点
        } 
        //复制随机节点
        cur = head;
        while(cur!=nullptr){
            Node* curNew = cur->next;
            curNew->random = cur->random==nullptr?nullptr:cur->random->next;
            cur = cur->next->next;
        }

        //拆分将A-A'-B-B'-C-C'拆分为A-B-C和A'-B'-C'
        Node* headNew = head->next;
        cur = head;
        Node* curNew = head->next; //还原之前的链表
        while(cur!=nullptr){
            cur->next = cur->next->next; 
            cur = cur->next;
            curNew->next = cur==nullptr?nullptr:cur->next;
            curNew = curNew->next; 
        }
        return headNew;

    }
};

0 赞同 0 条回复

zjl 普通 2022年10月24日下午7:38

借助hash表进行节点的映射

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

1 赞同 0 条回复

訁訁訁訁訁普通 2022年10月24日下午7:03

哈希表

/*
哈希表
利用哈希表的查询特点，考虑构建原链表节点和新链表节点的键值对映射关系，再遍历构建新链表的各节点的next和random即可
时间复杂度O(N)两轮遍历 空间复杂度O(N)哈希表使用线性大小的额外空间
*/
class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        HashMap<Node,Node> map = new HashMap<>();
        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);
    }
}

拼接加拆分

/**
拼接+拆分
时间复杂度O(N) 空间复杂度O(1)

考虑构建源节点1->新节点1->原节点2->新节点2->....的拼接链表，这样就可以在访问源节点random指向节点的同时找到对应新节点的random指向节点
最关键的代码
cur.next.random=cur.random.next;
cur.next.random是保存新节点的random域，因为cur.next为新节点
cur.random.next是指向新的random节点，cur.random是指向老的random节点
 */
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;//跳两步
        }//构建random域
        //拆分为两链表
        cur = head.next;
        Node pre = head,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 条回复

Y7n05h 普通 2022年10月24日下午6:55

class Solution {

public:
    Node *copyRandomList(Node *head) {
        for (auto *cur = head; cur;) {
            auto *newNode = new Node(cur->val);
            auto *tmp = cur->next;
            newNode->next = tmp;
            cur->next = newNode;
            cur = tmp;
        }
        for (auto *cur = head; cur;) {
            auto *newNode = cur->next;
            const auto *tmp = cur->random;
            newNode->random = tmp ? tmp->next : nullptr;
            cur = newNode->next;
        }
        Node *newhead;
        Node **end = &newhead;
        for (auto *cur = head; cur;) {
            *end = cur->next;
            cur->next = (*end)->next;
            cur = cur->next;
            end = &(*end)->next;
        }
        *end = nullptr;
        return newhead;
    }
}

时间复杂度：O(n)
空间复杂度：O(1) （返回值不计入）

0 赞同 0 条回复

@ 普通 2022年10月24日下午4:26

两次迭代遍历+哈希表，看了下题解，用递归可能跟简单一点

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

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


    }


}

0 赞同 0 条回复

忆霁昕永久会员 2022年10月24日下午3:42

将复制的节点插入原节点后面，即a->b->c => a->a’->b->b’->c->c’
可以在O(1)时间复杂度找到新链表的random节点，即 a’.random=a.random.next,最后要恢复原链表
时间O(n) 空间O(1)

class Solution {
    public Node copyRandomList(Node head) {
        //拆分 a->b->c => a->a'->b->b'->c->c'
        Node dummyHead = new Node(0);
        Node tail = dummyHead;
        Node p = head;
        while (p != null) {
            Node tmp = p.next;

            tail.next = p;
            tail = tail.next;
            //System.out.println(tail);
            Node newNode = new Node(p.val);
            tail.next = newNode;
            tail = newNode;
            //System.out.println(tail);
            p = tmp;
        }
        //复制random节点
        p = dummyHead.next;
        while (p != null) {
            if (p.random != null) {
                p.next.random = p.random.next;
            } else {
                p.next.random = null;
            }
            // System.out.println(p.random == null ? "null" : p.random);
            // System.out.println(p.next.random == null ? "null" : p.next.random);
            p = p.next.next;
        }
        //拆分
        Node resultHead = new Node(0);
        Node resultTail = resultHead;
        p = dummyHead.next;
        while (p != null) {

            resultTail.next = p.next;
            resultTail = resultTail.next;
            //复原原链表
            p.next = p.next.next;
            p = p.next;
        }

        // debug
        // p = resultHead.next;
        // while (p != null) {
        //     System.out.println(p.val);
        //     if (p.random != null) {
        //         System.out.println(p.random.val);
        //     } else {
        //         System.out.println("null");
        //     }
        //     p = p.next;
        // }
        return resultHead.next;
    }

}

0 赞同 0 条回复

刺猬普通 2022年10月24日下午3:40

class Solution {
public:
    Node* copyRandomList(Node* head) {
        /* 1. 判断链表是否为空 */
        if(head == nullptr) return nullptr;
        /* 2. 建立map容器 */
        Node* cur = head;
        unordered_map<Node*, Node*> map;
        /* 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射 */
        while(cur != nullptr) {
            map[cur] = new Node(cur->val);
            cur = cur->next;
        }
        cur = head;
        /* 4. 构建新链表的 next 和 random 指向 */
        while(cur != nullptr) {
            map[cur]->next = map[cur->next];
            map[cur]->random = map[cur->random];
            cur = cur->next;
        }
        /* 5. 返回新链表的头节点 */
        return map[head];
    }
};

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

0 赞同 0 条回复

Whatever 永久会员 2022年10月24日下午3:24

先进行原地复制，通过遍历对随机节点进行复制，过程中注意空节点的判断，之后将链表拆分成两条链表。时间复杂度O(n)，空间复杂度O(n)

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null){
            return null;
        }
        Node cur = head;
        while(cur != null){
            Node nxt = cur.next;
            Node temp = new Node(cur.val);
            cur.next = temp;
            cur.next.next = nxt;
            cur = nxt;
        }
        cur = head;
        while(cur != null){
            if(cur.random == null){
                cur.next.random = null;
            }else{
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }
        cur = head;
        Node newHead = head.next;
        Node 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;
    }
}

0 赞同 0 条回复

虾仁猪心普通 2022年10月24日下午2:13

思路：
1. 若头节点 head 为空节点，直接返回 null ；
2. 初始化一个HashMap map，指针cur 指向头节点；
3. 复制链表：
1）建立新节点，并向 map集合中添加键值对 (原 cur 节点, 新 cur 节点）；
2）cur 遍历至原链表下一节点；
4. 构建新链表的引用指向：
1）构建新节点的 next 和 random 引用指向；
2）cur 遍历至原链表下一节点；
5. 返回值：新链表的头节点 map[cur] ；
时间复杂度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;
        }
        Map<Node,Node> map = new HashMap<>();
        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);

    }
}

0 赞同 0 条回复

cxxz 普通 2022年10月24日下午12:01

将复杂问题分步完成：先创建每个节点的复制节点，然后再对每个节点的 random 进行复制，最后隔一拿一拆链。
注意要区 cur->next 的时候一定要先对 cur 进行空指针判断，同时合理使用 cur 和使用 cur->next 做为判断条件。

Node* copyRandomList(Node* head) {
        if (head == nullptr)
            return nullptr;

        // 复制节点
        Node * cur = head;
        while ( cur != nullptr )
        {
            Node *next = cur->next;
            Node *temp = new Node(cur->val);
            cur->next = temp;
            temp->next = next;
            cur = cur->next->next;
        }

        // 复制 random 字段
        cur = head;
        while ( cur != nullptr )
        {
            Node *curNew = cur->next;
            curNew->random = cur->random == nullptr ? nullptr:cur->random->next;
            cur = cur->next->next;
        }

        // 拆链
        Node *headNew = head->next;
        cur = head;
        Node *curNew = head->next;
        // 慎用 node->next
        while ( cur != nullptr )
        {
            cur->next = cur->next->next;
            cur = cur->next;
            // 访问 cur->next 时一定要对 cur 进行空指针判断
            curNew->next = cur == nullptr ? nullptr:cur->next;
            curNew = curNew->next;
        }
        return headNew;
    }

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

0 赞同 0 条回复

感到自己好渺小普通 2022年10月24日上午10:10

1.时间复杂度O(n)
2.空间复杂度O(1)
解题思路：
1.复制原结点的val值到新节点，并在每个原节点的后面添加一个val值相同的新节点
2.构造random
3.将复制好的新链表从新老链表拆出来
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head == NULL)
        {
            return NULL;
        }
        //1.复制原链表的val值，并将其接在原节点的后面
        //A->A'->B->B'->C->C'->NULL
        Node *cur = head;       //  cur是当前结点，指向原结点
        while(cur!=NULL)
        {
            Node *copyNode =new Node(cur->val);  // copyNode是要复制的新结点，A',B',C'
            copyNode->next = cur->next;   //  先让新结点指向原节点的下一个结点    A'->B
            cur->next = copyNode;        //  再让原结点连接在新结点上，A->A'->B
            cur = copyNode->next;        //再让cur指向下一个原节点B，继续复制
        }

        //2.构造random指针
        cur = head;
        while(cur!=NULL)
        {
            if(cur->random!=NULL)
            {
                cur->next->random = cur->random->next;  //cur->next->random A'的random域
            }                                           //cur->random->next A所指向的random域(B)的下一个新节点(B')，使A'的random指向B'
            cur = cur->next->next;  //到达下一个原结点
        }

        //3.将原链表和新链表相互分离
        cur = head;
        Node *newhead = head->next;
        while(cur->next!=NULL)
        {
            Node *temp = cur->next;
            cur->next = temp->next;
            cur = temp;
        }
        return newhead;
    }
};

0 赞同 0 条回复

啊哈普通 2022年10月24日上午12:17

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {

        //前置条件判断
        if(head == NULL) return head;
        if(head->val == val) {
            head = head -> next;
            return head;
        }

        //定义快慢指针
        ListNode* cur = head;
        ListNode* fast = head -> next;      
        while(fast != NULL){
            if(fast->val == val) {  //相同,则cur指针下一位指向fast下一位
                cur->next = fast->next;

            }

            //快慢指针同时移动一位
            cur = fast;
            fast = fast->next;  
        }

        //返回head
        return head;
    }
};

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

0 赞同 0 条回复

Gg 普通 2022年10月24日上午12:03

class Solution {
    public Node copyRandomList(Node head) {
        // 用存储新建的节点
        Map<Node,Node> map = new HashMap<>();
        Node curr = head;
        while(curr != null){
            map.put(curr,new Node(curr.val,null,null));
            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 条回复

浅夏的无奈普通 2022年10月23日下午11:41

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

class Solution {
    public Node copyRandomList(Node head) {
        if(head==null){
            return null;
        }
        //1. 复制节点，并构建拼接链表
        Node cur = head;
        while(cur!=null){
            Node tmp = new Node(cur.val);
            tmp.next = cur.next;
            cur.next = tmp;
            cur = tmp.next;
        }
        //2. 构建各新节点的 random 指向
        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,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 条回复

酥合普通 2022年10月23日下午9: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 temp = head;
        while(temp != null){
            Node tempNode = new Node(temp.val);
            tempNode.next = temp.next;
            temp.next = tempNode;
            temp = tempNode.next;
        }
        temp = head;
        while(temp != null) {
            temp.next.random = temp.random == null ? null : temp.random.next;
            temp = temp.next.next; 
        }
        temp = head;
        Node ans = head.next;
        Node ansTemp = head.next;
        while(temp != null){
            temp.next = temp.next.next;
            temp = temp.next;
            ansTemp.next = temp == null ? null : temp.next;
            ansTemp = ansTemp.next;
        }
        return ans;
    }
}

时间复杂度：O(n)

0 赞同 0 条回复

泡芙永久会员 2022年10月23日下午9:38

解法：原地（复制+拆分）
思路：1.对原链表的每个节点进行复制，并追加到原节点的后面 2.复制随机节点 3.拆分
Time：O(N)
Sapce ：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;
        }


        //复制random
        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 条回复

T 普通 2022年10月23日下午8:56

下面代码

class Solution {

    // hash表实现法
    public Node copyRandomList1(Node head) {
        if(head == null)
            return null;
        Node cur = head;
        HashMap<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);
    }

    // K神拼接法
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        Node cur = head;
        // 构建拼接链表， Node1 + Node1(new) + Node2 + Node2(new)...
        while(cur != null) {
            Node newNode = new Node(cur.val);
            newNode.next = cur.next;
            cur.next = newNode;
            cur = newNode.next;
        }
        cur = head;
        // random节点下一个就是新的random节点。
        while(cur != null) {
            if(cur.random != null) {
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }


        // 遍历拼接链表，拆分
        cur = head.next;
        Node tmp = head , res = head.next;
        while(cur.next != null) {
            tmp.next = tmp.next.next;
            cur.next = cur.next.next;
            tmp = tmp.next;
            cur = cur.next;           
        }
        tmp.next = null;
        return res;
    }
}

0 赞同 0 条回复

单个酒窝儿普通 2022年10月23日下午7:16

时间复杂度O(n)

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

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

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

0 赞同 0 条回复

Error 普通 2022年10月23日下午6:39

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        res_dict = {}
        cur = head
        while cur:
            res_dict[cur] = Node(cur.val)
            cur = cur.next
        cur = head
        while cur:
            res_dict[cur].next = res_dict.get(cur.next)
            res_dict[cur].random = res_dict.get(cur.random)
            cur = cur.next

        return res_dict.get(head)

时间复杂度 O（n）

0 赞同 0 条回复

just 普通 2022年10月23日下午5:43

//使用map
class Solution {
public:
Node* copyRandomList(Node* head) {
unordered_map<Node,Node> map;
Node* cur=head;
Node* dummy=new Node(0);
Node* pre=dummy;
while(cur){
Node* newnode=new Node(cur->val);
map[cur]=newnode;
pre->next=newnode;
pre=pre->next;
cur=cur->next;
}
cur=head;
Node* start=dummy->next;
while(cur){
if(cur->random!=nullptr){
auto it=map.find(cur);
it->second->random=map.find(cur->random)->second;
}
cur=cur->next;
}
return dummy->next;
}
};

0 赞同 0 条回复

绍熙普通 2022年10月23日下午5:42

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        Node cur = head;
        // 1. 复制各节点，并构建拼接链表
        while(cur != null) {
            Node tmp = new Node(cur.val);
            tmp.next = cur.next;
            cur.next = tmp;
            cur = tmp.next;
        }
        // 2. 构建各新节点的 random 指向
        cur = head;
        while(cur != null) {
            if(cur.random != null)
                cur.next.random = cur.random.next;
            cur = cur.next.next;
        }
        // 3. 拆分两链表
        cur = head.next;
        Node pre = head, 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 条回复

是梦终空永久会员 2022年10月23日下午5:36

时间O(n)
空间O(n)
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;
        }

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

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

0 赞同 0 条回复

Haoyun 普通 2022年10月23日下午5:21

var copyRandomList = function(head) {
   if(!head) return head;
   let map = new Map();
   let newHead = new Node();
   let newCur = newHead;
   let cur = head;
//先不考虑random，和普通链表一样复制，用map记录新旧节点映射关系
   while(cur) {
       newCur.val = cur.val;
       newCur.next = cur.next ? new Node() : null;
       map.set(cur, newCur);
       cur = cur.next;
       newCur = newCur.next;
   }
   newCur = newHead;
//遍历原链表和新链表，找到原链表各节点的random,通过map找到对应新random
   while(head) {
       newCur.random = head.random ? map.get(head.random) : null;
       newCur = newCur.next;
       head = head.next;
   }
   return newHead;
};

时间：O(n)
空间：O(n)

0 赞同 0 条回复

糖香香普通 2022年10月23日下午5:09

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;
        //建立新链表的next和random指向
        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 条回复

Chin 普通 2022年10月23日下午4:39

class Solution {
    public Node copyRandomList(Node head) {
        if(head==null) return head;
        //  map存储原节点和新节点的映射
        Map<Node,Node> map = new HashMap<>();
        Node cur = head;
        //  先存简单映射
        while(cur != null){
            map.put(cur, new Node(cur.val, null, null));
            cur = cur.next;
        }

        //  从map中取到并赋next 和random 的值
        Node cur2 = head;
        while(cur2 != null){
            map.get(cur2).next = map.get(cur2.next);
            map.get(cur2).random = map.get(cur2.random);
            cur2 = cur2.next;
        }
        return map.get(head);
    }
}

哈希迭代，时空复杂度On

0 赞同 0 条回复

宁永久会员 2022年10月23日下午4:18

一开始没有考虑head为空的时候

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null){
            return null;
        }
        //复制链表节点 复制随机节点 拆分
        Node cur = head;
        while(cur != null){
            Node newNode = new Node(cur.val);
            Node temp = cur.next;
            cur.next = newNode;
            newNode.next = temp;
            cur = cur.next.next;
        }
        // copy random A  A1   B   B1
        cur = head;
        while(cur != null){
            cur.next.random = (cur.random == null)? null : cur.random.next;
            cur = cur.next.next;
        }
        cur = head;
        Node ret = head.next;
        while(cur != null){
            Node newNode = cur.next;
            cur.next = newNode.next;
            newNode.next = (cur.next == null)? null :cur.next.next;
            cur = cur.next;
        }
        return ret;

    }
}

0 赞同 0 条回复

追普通 2022年10月23日下午4:17

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head == nullptr) 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;
    }
};

先复制一份链表，然后再拆分（指针部分搞得迷迷糊糊的）

0 赞同 0 条回复

猫猫真可爱普通 2022年10月23日下午4:13

看题解了，先打卡

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

0 赞同 0 条回复

yanshuojune 普通 2022年10月23日下午3:51

解体思路：创建新的链表，每个原节点后跟一个复制节点，随后遍历链表让复制节点的random指针指向前一个原节点的random指针的next，随后再拆分链表，得到复制后的结果。
时间复杂度：O(n)
空间复杂度：O(1)

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return None
        # 在每个节点后面创建新的节点
        p = head
        while p:
            new_node = Node(p.val,None,None)
            new_node.next = p.next
            p.next = new_node
            p = new_node.next
        # 设置新节点的随机节点
        p = head
        while p:
            if p.random:
                p.next.random = p.random.next
            p = p.next.next
        # 拆分链表为原链表和新链表
        dummy = Node(-1)
        p = head
        curr = dummy
        while p:
            curr.next = p.next
            curr = curr.next
            p.next = curr.next
            p = p.next
        return dummy.next

0 赞同 0 条回复

派大星普通 2022年10月23日下午3:50

//先建立链表，最后再整合随机指针
//时间复杂度O(n^2)
//空间复杂度O(1)
class Solution {
    public Node copyRandomList(Node head) {
        if(head == null){
        return null;                             
    }
    Node newList = new Node(0);
    Node newTemp = newList;
    newList.val = head.val;
    Node temp1 = head.next;
    while(temp1 != null){
        Node l = new Node(0);
        l.val = temp1.val;
        newTemp.next = l;
        newTemp = newTemp.next;
        temp1 = temp1.next;
    }
    newTemp = newList;
    Node newTemp2 = newList;//当前新节点添加random位置
    Node newTemp3 = newList;//来回遍历的指针
    Node temp2 = head;//旧节点查询random位置
    Node temp3 = head;//来回遍历的指针
    while(temp2 != null){
        if(temp2.random == null){
            newTemp2.random = null;
            temp2 = temp2.next;
            newTemp2 = newTemp2.next;
        }else{
            int i = 0;  //指针移动了几次到达的位置
            while(temp3 != temp2.random && temp3!=null){
                temp3 = temp3.next;
                i++;
            }
            if(i==0){
                newTemp2.random = newTemp;
                temp2 = temp2.next;
                newTemp2 = newTemp2.next;
            }else{
                for (int j = 0; (j < i)&&(newTemp3!=null); j++) {
                    newTemp3 = newTemp3.next;
                }
                newTemp2.random = newTemp3;
                temp2 = temp2.next;
                newTemp2 = newTemp2.next;
            }
            newTemp3 = newTemp;
            temp3 = head;
        }
    }
    return newList;
    }
}

0 赞同 0 条回复

小肸永久会员 2022年10月23日下午1:51

思路一：暴力。用两个Node型的动态数组ArrayList，一个为temp，另一个为res，temp存放原链表的每一个节点，res存放复制过来的每一个节点（节点中next指针域和random指针域都没有赋值），然后遍历res，给res中每一个节点的next指针域和random指针域赋值。时间复杂度O(N)，空间复杂度O(N)。

class Solution {
    private List<Node> temp = new ArrayList<>();
    private List<Node> res = new ArrayList<>();
    public Node copyRandomList(Node head) {
        while (head != null) {
            Node node = new Node(head.val);
            temp.add(head);
            res.add(node);
            head = head.next;
        }
        for (int i = 0; i < res.size(); i ++) {
            res.get(i).random = (temp.get(i).random == null ? null : res.get(temp.indexOf(temp.get(i).random)));
            if (i != res.size() - 1) {
                res.get(i).next = res.get(i + 1);
            }
        }
        return res.size() == 0 ? null : res.get(0);
    }
}

思路二：其实思路一用两个动态数组来存放新的复制链表中random节点与原链表的节点的对应关系。可以用一个哈希结构来替换两个动态数组。时间复杂度O(N)，空间复杂度O(N)。

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

思路三：解决本题的核心就是要知道新链表中每一个节点random节点在新链表的位置。直接在原链表上复制每一个节点在原节点的后面（复制操作），1->2->3复制后为1->1->2->2->3->3。再让新的复制节点的random的指针域指向原节点指针的下一个节点，最后把新链表从原链表拆分出来。（拆分操作）时间复制度O(N)，空间复杂度O(1)（返回的结果链表不计入）。

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

思路四：思路二是哈希+迭代实现。可以用哈希+递归实现。

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

0 赞同 0 条回复

Asphyxia 普通 2022年10月23日下午1:14

哈希表记住映射关系，然后先走一遍建立单链表，再串random

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
       unordered_map<RandomListNode*,RandomListNode*> m;
       RandomListNode* node = pHead;
       RandomListNode* n_node = NULL;
       if(node!=NULL) n_node = new RandomListNode(node->label);
       RandomListNode* ret = n_node;
       m[node] = n_node;
        while(node){
            RandomListNode* n_nex_node = NULL;
            if(node->next!=NULL){
                n_nex_node = new RandomListNode(node->next->label);
            }
            n_node->next = n_nex_node;
            n_node = n_nex_node;
            node = node->next;
            m[node] = n_node;
        }
        n_node = ret;
        node = pHead;
        while(n_node){
            n_node->random = m[node->random];
            n_node = n_node->next;
            node = node->next;
        }
        return ret;
    }
};

0 赞同 0 条回复

wxc 普通 2022年10月23日下午12:07

额

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return None
        #复制节点
        f = head
        while f :
            x = Node(f.val)
            x.next = f.next
            f.next = x
            f = x.next
        #复制random
        f = head
        while f :
            f.next.random = f.random.next if f.random else None
            f = f.next.next
        #拆分
        l1 = l2 = head.next
        pre = head
        while l1.next :
            pre.next = pre.next.next
            l1.next = l1.next.next
            pre = pre.next
            l1 = l1.next
        pre.next = None
        return l2

0 赞同 0 条回复

潜行1 我是火车王！普通 2022年10月23日下午12:03

复制链表并拆分

func copyRandomList(head *Node) *Node {
    // 要实际复制，不然可以检测出来
    // return head
    if head == nil {
        return head
    }

    cur := head
    // 复制链表结点
    for cur != nil {
        next := cur.Next
        cur.Next = &Node{
            Val:    cur.Val,
            Next:   nil,
            Random: nil,
        }

        cur.Next.Next = next
        cur = next
    }

    // 复制随机结点
    cur = head
    for cur != nil {
        curNew := cur.Next
        if cur.Random != nil {
            curNew.Random = cur.Random.Next
        } else {
            curNew.Random = nil
        }
        cur = cur.Next.Next
    }

    // 拆分成两个链表
    headNew := head.Next
    cur = head
    curNew := head.Next
    for cur != nil {
        cur.Next = cur.Next.Next
        cur = cur.Next
        if cur == nil {
            curNew.Next = nil
        } else {
            curNew.Next = cur.Next
        }
        curNew = curNew.Next
    }

    return headNew
}

0 赞同 0 条回复

你有点可爱喔普通 2022年10月23日上午11:38

本题最优的解法是复制链表，进行拆分。复制一个新的节点在原有节点之后，如 1 -> 2 -> 3 -> null 复制完就是 1 -> 1 -> 2 -> 2 -> 3 – > 3 -> null。然后从头开始遍历链表，将复制的链表与随机指针进行串联，前提要进行判断，保证数据是否为空。最后将链表进行拆分，得到了复制的链表。
时间复杂度O(n),空间复杂度O(1);

 public Node copyRandomList(Node head) {
        if(head == null){
            return null;
        }
        //复制节点
        Node cur = head;
        while(cur != null){
            //保存节点
            Node temp = cur.next;
            cur.next = new Node(cur.val);
            cur.next.next = temp;
            cur = temp;
        }
        //
        cur = head;
        while(cur != null){
            Node randomNode = cur.next;
            randomNode.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 条回复

黎昕普通 2022年10月23日上午12:22

关键点：p->next->random=p->random->next;

时间复杂度：O(n)

空间复杂度：O(1)

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head==NULL)return NULL;
        // 第一次复制
        Node* p=head;
        while(p!=NULL){
            Node* tmp=new Node(p->val);
            tmp->next=p->next;
            p->next=tmp;
            p=tmp->next;
        }
        // 设置复制节点的random指针
        p=head;
        while(p!=NULL){
            if(p->random==NULL){
                p->next->random=NULL;
            }
            else{
                p->next->random=p->random->next;
            }
            p=p->next->next;
        }
        // 分离两个链表
        Node* p1=head;
        Node* p2=head->next;
        Node* newhead=p2;
        while(p1!=NULL){
            p1->next=p2->next;
            p1=p2->next;
            if(p1==NULL)break;
            p2->next=p1->next;
            p2=p1->next;
        }
        return newhead;
    }
};

0 赞同 0 条回复

狗蛋儿普通 2022年10月22日下午11:14

这个题目难在这个理解复制是指的深拷贝

深拷贝意味着每个节点都是新的区别之前地址的存储空间

因此拷贝是需要区分两个过程

第一个过程先单纯的把直线链接链接起来

第二个过程再把random链接起来

class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        if(!pHead) return pHead;
        unordered_map<RandomListNode *, RandomListNode *> map;
        RandomListNode *dummy = new RandomListNode(0);
        RandomListNode *pre = dummy,*cur = pHead;

        while(cur){
            RandomListNode *clone = new RandomListNode(cur->label);
            pre->next = clone;
            map[cur] = clone;
            pre = pre-> next;
            cur = cur-> next;
        }

        for(auto& [key,value] : map){
            value->random = key->random == NULL ? NULL: map[key->random]; 
        }
        return map[pHead];
    }
};

0 赞同 0 条回复

天然普通 2022年10月22日下午10:35

看的题解，原本想法是像普通链表一样先建立，random用字典去记住，再遍历一遍新链表的同时给random赋值

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 head
        dir = {}
        cur = head
        while cur != None:
            dir[cur] = Node(cur.val)
            cur = cur.next

        cur = head

        while cur != None:
            dir[cur].next = dir.get(cur.next)
            dir[cur].random = dir.get(cur.random)
            cur = cur.next

        return dir[head]

1 赞同 0 条回复

青木普通 2022年10月22日下午10:33

//用字典记录键值对，直接就可以random到对应位置了，不会用HashMap T_T
class Solution {
    public Node copyRandomList(Node head) {
        Map<Node, Node> map = new HashMap<>();
        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);
    }
}
//空间复杂度O(n)
//时间复杂度O(n)


//拆分确实减少了额外的空间，但是较为绕弯
class Solution {
    public Node copyRandomList(Node head) {
        if(head==null) return null;
        Node cur = head;
        //插入节点
        while(cur != null){
            Node newNode = new Node(cur.val);
            newNode.next = cur.next;
            cur.next = newNode;
            cur = newNode.next;
        }
        //连接节点
        cur = head;
        while(cur != null){
            if(cur.random != null){
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }
        //拆分节点
        Node pre = head, res = head.next;
        cur = 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;
    }
}
//空间复杂度O(1)
//时间复杂度O(n)

1 赞同 0 条回复

mpweixin用户普通 2022年10月22日下午10:28

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        Node p = head;
        while(p != null){                           // 在每个节点后，复制节点，组成一个链表
            Node temp = p.next;
            Node copy = new Node(p.val);
            p.next = copy;
            copy.next= temp;
            p = temp;
        }
        p = head;
        while(p != null){
            if(p.random == null)
                p.next.random = null;
            else
                p.next.random = p.random.next;      // 复制节点的random = 原节点->random->next
            p = p.next.next;
        }
        p = head;
        Node res = head.next;
        Node k = res;
        while(p != null){                           // 拆分成两个链表
            if(k.next == null){
                p.next = null;
                break;
            }
            p.next = k.next;
            p = p.next;
            k.next = p.next;
            k = k.next;
        }
        return res;
    }
}

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

0 赞同 0 条回复

波波_1936 普通 2022年10月22日下午10:11

    public Node copyRandomList(Node head) {
        if (head == null ) return head;
        Node res = head;
        HashMap<Node, Node> nodeList = new HashMap<>();

        Node tp = head;
        while (tp != null) {
            //存了原节点和新节点的映射
            nodeList.put(tp, new Node(tp.val));
            tp = tp.next;
        }
        while (head != null) {
            //更新next 和random节点，不能和原节点在一个循环是因为random可能指向的节点还没映射到
            nodeList.get(head).next = nodeList.get(head.next);
            nodeList.get(head).random = nodeList.get(head.random);
            head = head.next;
        }
        return nodeList.get(res);
    }

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

0 赞同 0 条回复

易水寒永久会员 2022年10月22日下午9:51

哈希表

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

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年10月22日下午9:22

之前做过一遍，还是写了挺久

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) return head;
        Node cur = head;
        while(cur!=null){
            Node node = new Node(cur.val);
            Node temp = cur.next;
            node.next = cur.next;
            cur.next = node;
            cur = temp;
        }
        cur = head;
        while(cur!=null){
            if(cur.random == null){
                cur.next.random = null;
            }else{
                 cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }
        cur = head;
        Node curNew = head.next;
        Node result = head.next;
        while(cur!=null){
            cur.next = cur.next.next;
            //这块之前老出问题，就是不能出现null.next这种情况
            curNew.next = cur.next==null?null:cur.next.next;
            cur = cur.next;
            curNew = curNew.next;
        }
        return result;
    }
}

1 赞同 0 条回复

So 普通 2022年10月22日下午9:06

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

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

0 赞同 0 条回复

一只骆驼普通 2022年10月22日下午8:17

先用哈希把节点拷贝一份，再在复制的时候从哈希中调
时间空间都是O(n)

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 条回复

1ue1uekin8 普通 2022年10月22日下午8:03

时间空间都是O(n),

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return head;
        }
        //map中存的是(原节点，拷贝节点)的一个映射
        Map<Node, Node> map = new HashMap<>();
        for (Node cur = head; cur != null; cur = cur.next) {
            map.put(cur, new Node(cur.val));
        }
        //将拷贝的新的节点组织成一个链表
        for (Node cur = head; cur != null; cur = cur.next) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
        }

        return map.get(head);
    }
}

0 赞同 0 条回复

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

共以下 69 个回答

这个题目难在这个理解复制是指的深拷贝

深拷贝意味着每个节点都是新的区别之前地址的存储空间

因此拷贝是需要区分两个过程

第一个过程先单纯的把直线链接链接起来

第二个过程再把random链接起来

# 回答此问题取消回复

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

共以下 69 个回答

这个题目难在这个理解复制是指的深拷贝

深拷贝意味着每个节点都是新的区别之前地址的存储空间

因此拷贝是需要区分两个过程

第一个过程先单纯的把直线链接链接起来

第二个过程再把random链接起来

# 回答此问题 取消回复

# 回答此问题取消回复