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

招舟子普通 2023年8月24日下午10:38

/*
// 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 tmp = head;
while(tmp!=null){
Node next = tmp.next;
tmp.next = new Node(tmp.val);
tmp.next.next = next;
tmp = next;
}
tmp = head;
while(tmp!=null){
Node next = tmp.next;
tmp.next.random = tmp.randomnull?null:tmp.random.next;
tmp = tmp.next.next ;
}

    tmp = head;
    Node tmp_1 = head.next;
    Node res = head.next;
    while(tmp_1.next!=null){
        tmp.next = tmp.next.next;
        tmp_1.next  = tmp_1.next.next;
        tmp= tmp.next;
        tmp_1 = tmp_1.next;
    }
    tmp.next = null;
    return res;
}

}
先复制原节点顺序，再复制random顺序，再拆分

0 赞同 0 条回复

mpweixin用户普通 2023年7月18日下午11:54

时间复杂度：O(n)
空间复杂度：O(1)
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){
        //cur.random可能为null 需要判断
        cur.next.random = cur.random == null ? null : cur.random.next;
        cur = cur.next.next;
    }

    //拆分链表
    Node newHead = head.next;
    cur = head;
    Node curHead = head.next;
    while(cur != null){
        cur.next = curHead.next;
        cur = cur.next;
        //结束条件cur == null,此时cur.next会报错，需要判断
        curHead.next = cur == null ? null : cur.next; 
        curHead = curHead.next;
    }
    return newHead;



}

}

0 赞同 0 条回复

与你同行普通 2023年7月17日下午3:10

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

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

    //复制Next节点
    cur := head
    for cur != nil {
        next := cur.Next
        cur.Next = &Node{Val: cur.Val}
        cur.Next.Next = next
        cur = next
    }

    //复制Random节点
    cur = head
    for cur != nil {
        curNew := cur.Next
        if cur.Random != nil {
            //新链表节点的 random 指针指向旧链表对应节点的 random 指针的下一个值
            curNew.Random = cur.Random.Next
        }
        cur = cur.Next.Next
    }

    //把原链表的复制Next节点，复制Random节点， 断开连接关系
    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 条回复

橙子陈普通 2023年7月15日下午9:56

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

        // 复制链表节点
        Node cur = head;
        while (null != cur) { 
            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(n)

0 赞同 0 条回复

ZJS 永久会员 2023年7月15日下午12:15

时间复杂度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 head;
        }


        // 复制链表节点
        Node curr = head;
        while(curr != null){
            Node next = curr.next;
            curr.next = new Node(curr.val);
            curr.next.next = next;
            curr = next;
        }

        //复制随机指针
        curr = head;
        while(curr != null){
            Node currNew = curr.next;
            currNew.random = curr.random == null ? null : curr.random.next;
            curr = curr.next.next;
        }

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

        return headNew;
    }
}

0 赞同 0 条回复

TT 永久会员 2023年7月10日下午4:11

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

0 赞同 0 条回复

往远处看普通 2023年7月8日上午10:51

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

代码

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

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    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;
        }

        // 拆分,比如把 A->A1->B->B1->C->C1拆分成 A->B->C和A1->B1->C1
        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 条回复

淡色花樱普通 2023年7月3日下午8:24

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

0 赞同 0 条回复

Gracelyne 普通 2023年7月3日上午11:30

时间：O(n) 空间：O(n)
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head == nullptr) return nullptr;
        Node* cur = head;
        map<Node*, Node*> mp; //哈希表
        while(cur != nullptr){
            mp[cur] = new Node(cur->val); //在原节点建立新节点
            cur = cur->next;
        }
        cur = head;
        while(cur != nullptr){
            mp[cur]->next = mp[cur->next];
            mp[cur]->random = mp[cur->random];
            cur = cur->next;
        }
        return mp[head];
    }
};

0 赞同 0 条回复

mpweixin用户永久会员 2023年7月1日下午12:56

复制，分离

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

0 赞同 0 条回复

mpweixin用户普通 2023年6月29日下午1:16

java
/*
// 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;
        Node tmp;
        //先复制链表,将两条链表合在一起 A->A1->B.....
        while(cur != null) {
            tmp = cur.next;
            Node tmpCell = new Node(cur.val);
            cur.next = tmpCell;
            tmpCell.next = tmp;
            cur = tmp;
        }
        // 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) {
            cur.next.random = (cur.random == null) ? null : cur.random.next;
            cur = cur.next.next;
        }
        // while(cur != null) {
        //     Node curNew = cur.next;
        //     curNew.random = cur.random == null ? null : cur.random.next;
        //     cur = cur.next.next;
        // }

        //对链表进行拆分
        cur = head;
        Node headNew = head.next; //headNew用于存储拆分后链表的头结点
        while(cur.next != null) {
            tmp = cur.next;
            cur.next = tmp.next;
            cur = tmp;
        }
        // cur = head;
        // Node headNew = head.next;
        // 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 条回复

大大普通 2023年6月29日上午8:24


//  利用map创建映射
class Solution {
    public Node copyRandomList(Node head) {
        HashMap h=new HashMap();
        Node temp=head;
        Node cur=head;
        //创建节点
        while(temp!=null){
          h.put(temp,new Node(temp.val));
          temp=temp.next;
        }
        //进行连接节点
        while(cur!=null){
            h.get(cur).next=h.get(cur.next);
            h.get(cur).random=h.get(cur.random);
            cur=cur.next;
        }
        return h.get(head);
    }
}

java//自己创建映射

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
             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;//pre在前 cur在后
         Node pre=head,res=pre.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 条回复

Sexypig. 普通 2023年6月28日下午10:42

代码：

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        HashMap={}
        for p in [head]:
            while p:
                if p not in HashMap:
                    HashMap[p]=Node(p.val)
                p=p.next
        for p in [head]:
            while p:
                if p.next:
                    HashMap[p].next=HashMap[p.next]
                if p.random:
                    HashMap[p].random=HashMap[p.random]
                p=p.next
        return HashMap.get(head)

思路：
通过字典映射，将原本的链表和新链表对应起来。第一次遍历生成新链表（未连接，只赋值），第二次遍历连接新链表。
时间：遍历两次链表，O（n）
空间：用了大小为链表长度的辅助字典，O（n）

0 赞同 0 条回复

泡芙永久会员 2023年6月27日下午9:39

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

        // 复制链表节点
        Node cur = head;
        while (cur != null) {
            Node next = cur.next;
            cur.next = new Node(cur.val);
            cur.next.next = next;
            cur = next;
        }

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

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

0 赞同 0 条回复

Tang 普通 2023年6月26日下午6:59

/*
// 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 Map<Node, Node> copyMap = new HashMap<>();
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        if (!copyMap.containsKey(head)) {
            Node newNode = new Node(head.val);
            copyMap.put(head, newNode);
            newNode.next = copyRandomList(head.next);
            newNode.random = copyRandomList(head.random);
        }
        return copyMap.get(head);
    }
}

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

0 赞同 0 条回复

mpweixin用户永久会员 2023年6月26日下午1:58

打卡

var copyRandomList = function(head) {
    if(head == null){
        return null;
    }

    // 使用复制 + 拆分的方法
    // 复制链表节点
    let cur = head;
    while(cur != null){
        // 保存cur.next
        let next = cur.next;
        cur.next = new Node(cur.val);
        cur.next.next = next;
        cur = cur.next.next;
    }

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

    // 拆分
    cur = head;
    let newHead = head.next;
    let newCur = newHead;
    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 条回复

HU 普通 2023年6月25日下午10:21

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

    // 1. 先复制链表节点
    let cur = head;
    while(cur !== null) {
        // 先保存cur的下一个节点
        let temp = cur.next;
        cur.next = new Node(cur.val);
        cur.next.next = temp;
        // 向后移动一步
        cur = temp;
    }

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

    // 3. 拆分
    cur = head;
    let headNew = head.next;
    let 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 条回复

GGBond 普通 2023年6月25日下午8:17

如果是普通链表，我们可以直接按照遍历的顺序创建链表节点。而本题中因为随机指针的存在，当我们拷贝节点时，「当前节点的随机指针指向的节点」可能还没创建
class Solution {
    //这题看起来不难，细节很多
    public Node copyRandomList(Node head) {
        //复制每个结点，插入到结点之后 A->A`->B->B`...->null
        //先设置随机结点，再重新设置复制结点的next值
        //不能改变原链表
        if(head == null){
            return null;
        }
        Node p = head;
        while(p != null){
            //A->A`->B->B`..
            Node node = new Node(p.val);
            node.next = p.next;
            p.next = node;
            p = p.next.next;
        }
        //设置复制结点的随机结点
        p = head;
        while(p != null){
            //random结点可能为空
            if(p.random != null){
                p.next.random = p.random.next;
            }
            p = p.next.next;
        }

        //重新设置复制结点的next值
        p = head;
        Node newHead = head.next;
        while(p != null){
            Node temp = p.next.next;
            if(temp == null){
                //说明当前是（C->C`->null）
                p.next.next = temp;
            }else{
                p.next.next = temp.next;
            }

            p.next = temp;
            p = temp;
        }
        return newHead;
    }
}

0 赞同 0 条回复

普通 2023年6月25日上午10:20

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

构建hash表，时间复杂度O(n)空间复杂度O(n)

0 赞同 0 条回复

mpweixin用户普通 2023年6月24日下午10:32

拆分链表

/*
// 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 copyNode = new Node(cur.val);
            copyNode.next = cur.next;

            Node tmp = cur.next;
            cur.next = copyNode;
            cur = tmp;
        }

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


        Node newHead = head.next;
        Node curNew = head.next;
       Node current = head;
        //a->a1->b->b1
         while(current !=null) {       
            Node tmp = current.next.next;
            current.next = tmp;
            curNew.next = tmp == null ? null : tmp.next;

            current = current.next;
            curNew = curNew.next;
         }

        return newHead;
    }
}

0 赞同 0 条回复

BOZ 普通 2023年6月24日下午10:03

【思路】这题比较容易出错，通过先复制后拆分的方法完成，共需要三次遍历链表
【复杂度】时间O(n)，空间O(1)

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

        // node copy
        Node *curr = head;
        while(curr != NULL) {
            Node *curr_copy = new Node(curr->val);
            curr_copy->next = curr->next;
            curr->next = curr_copy;
            curr = curr_copy->next;
        }

        // random pointer copy
        curr = head;
        while(curr != NULL) {
            Node *curr_copy = curr->next;
            curr_copy->random = curr->random == NULL? NULL: curr->random->next;
            curr = curr_copy->next;
        }

        // seperate list into two independent list
        Node *new_head = head->next;
        curr = head;
        while(curr->next != NULL) {
            Node *tmp = curr->next;
            curr->next = curr->next->next;
            curr = tmp;
        }

        return new_head;
    }
};

0 赞同 0 条回复

未来已来~ 普通 2023年6月24日下午5:48

/*
 *  Java 代码
 * 复杂度分析: 
 *      时间复杂度: O(n) ,三轮遍历链表，使用O(N) 时间。
 *      空间复杂度: O(1), 节点引用变量使用常数大小的额外空间
 *
*/
class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }

        Node cur = head;
        // 1. 复制各链表结点,并构建拼接链表
        while (cur != null) {
            Node oldNext = cur.next; // 暂存原结点指向
            cur.next = new Node(cur.val);
            // A->A1->B->B1->C->C1...
            cur.next.next = oldNext;
            cur = oldNext;
        }

        // 2. 复制随机结点,各新节点的 random 指向
        cur = head;
        while(cur != null) {
            if(cur.random != null)
                cur.next.random = cur.random.next;
            cur = cur.next.next;
        }

        // 3. 拆分俩链表: 如把 A->A1->B->B1->C->C1拆分成 A->B->C和A1->B1->C1
        cur = head.next;
        Node pre = head , result = 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 result;   // 返回新链表头节点
    }
}

0 赞同 0 条回复

3_🔥 永久会员 2023年6月23日下午9:38

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null)
            return null;
        //1.复制 变成A->A`->B->B`这样
        Node cur = head;
        while(cur != null){
            Node next = cur.next;
            cur.next = new Node(cur.val);
            cur.next.next = next;
            cur = next;
        }
        //2.复制随机节点random 
        cur = head;
        while(cur != null){
            Node curNew = cur.next;
            curNew.random = cur.random==null?null:cur.random.next;
            cur = cur.next.next;
        }
        //3.拆分
        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 条回复

Yodl. 普通 2023年6月23日下午12:00

哈希表 时间复杂度O(n) 空间复杂度O(n)
class Solution {
public:
    Node* copyRandomList(Node* head) {
        Node* h=head;
        unordered_map map;
        while(h!=NULL){          
            map[h]=new Node(h->val);//先复制节点值，原节点-》新的节点，且新节点值为原节点值
            h=h->next;
        }
        h=head; //h再次指向原链表头节点
        while(h!=NULL){
            map[h]->next=map[h->next]; //连接新链表仅针对map中产生的新节点，不能把map中的节点指向原来的链表中的节点
            map[h]->random=map[h->random];
            h=h->next;
        }
        return map[head];

    }
};

原地复制节点 时间复杂度O（n） 空间复杂度O（1）
Node* copyRandomList(Node* head) {
        if(!head) 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 条回复

彦，，# 普通 2023年6月22日下午11:35

没写出来，看了思路，这题直接在原地复制节点的思想很赞
时间复杂度O（n）
空间复杂度O（1）

Node* copyRandomList(Node* head) {
        if(!head) 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 条回复

残月冷骄阳普通 2023年6月22日下午10: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) {
        if(head==null){
            return null;
        }

        //复制节点
        for(Node node =head;node !=null;node = node.next.next ){
           Node  newCur = new Node(node.val);
            newCur.next = node.next;
            node.next = newCur;
        }

        //复制random节点
        for(Node node = head; node!=null;node = node.next.next){
            Node newNode = node.next;
            newNode.random = node.random!=null?node.random.next:null;
        }
        //拆解链表
        Node newHead = head.next;
        for(Node node = head;node!=null;node = node.next){
            Node  nodeNew = node.next;
            node.next  = node.next.next;
            nodeNew.next = nodeNew.next!=null?nodeNew.next.next:null;

        }

        return newHead;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年6月22日下午10:21

//注意空引用的问题若next为null，则next.next会报错

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;

        }

        //复制random指针
        cur = head;
        while(cur != null){
            cur.next.random =  cur.random == null ? null : cur.random.next;
            cur = cur.next.next;
        }

        //拆分
        cur = head;
        Node newHead = head.next;
        while(cur != null){
            Node temp1 = null;
            Node temp2 = null;

            if(cur.next != null){
                temp2 = cur.next.next;
            }
            else{
                temp2 = null;
            }

           if(cur.next.next != null){
                temp1 = cur.next.next.next;
           }
           else{
                temp1 = null;
           }

            cur.next.next = temp1;
            cur.next = temp2;

            cur = cur.next;
        }

        return newHead;       
    }

0 赞同 0 条回复

mpweixin用户普通 2023年6月22日下午5:43

哈希表 时间复杂度O(n) 空间复杂度O(n)
"""
# 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
"""
dic = {}
class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return None
        if head not in dic:
            tmp = Node(head.val)
            dic[head] = tmp
            tmp.next = self.copyRandomList(head.next)
            tmp.random = self.copyRandomList(head.random)
        return dic[head]

0 赞同 0 条回复

CV大神普通 2023年6月22日下午4:57

“`java
public Node copyRandomList(Node head) {
if (head == null) {
return head;
}
Node current = head;
Map maps = new HashMap<>();
//复制全部节点
while (current != null) {
//本体为key，复制的分身为value
maps.put(current, new Node(current.val));
current = current.next;
}
//处理每个节点的next和random
current = head;//从头开始
while (current != null) {
//当前节点的分身的next指向原节点的next的分身
maps.get(current).next = maps.get(current.next);
//当前节点的分身的random指向原节点的random的分身
maps.get(current).random = maps.get(current.random);
current = current.next;
}
//新链表的分身就是head为key的value
return maps.get(head);

“`java
时间复杂度O(n)，空间复杂度O(n)

0 赞同 0 条回复

别恰冰水🧊 永久会员 2023年6月21日下午11:28

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

}

0 赞同 0 条回复

Dsjh 普通 2023年6月21日下午4:06

“`c++
class Solution {
public:
Node* copyRandomList(Node* head) {
// 用map快速查询next和random指向的节点
unordered_map m;
// 先对值进行拷贝
for(Node* cur = head;cur;cur=cur->next){
m[cur] = new Node(cur->val);
}
// 再对next和random拷贝
for(Node* cur = head;cur;cur=cur->next){
if(cur->next) m[cur]->next = m[cur->next];
if(cur->random) m[cur]->random = m[cur->random];
}
return m[head];
}
};

0 赞同 0 条回复

断舍离永久会员 2023年6月21日下午3:56

//完全不理解，看的题解呜呜呜呜
class Solution {
    public Map<Node,Node> map = new HashMap<>();
    public Node copyRandomList(Node head) {
        // 终止条件next给过来的node为null；
        if(head == null){
            return null;
        }
        // 中间处理方法
        // 1. 递归创建节点到最后一个节点，并吧所有创建的节点保存在map中；
        Node newNode = new Node(head.val);
        map.put(head,newNode);
        newNode.next = copyRandomList(head.next);
        // 2. 因为递归过程中会创建所有的节点，所以回溯过程中直接进行newNode.random赋值
        newNode.random = map.get(head.random);
        return newNode;
    }
}

0 赞同 0 条回复

张开怀普通 2023年6月21日下午3:40

“`cpp
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;
}
// 拆分，比如把A->A1->B->B1->C->C1 拆分成 A->B->C 和 A1->B1->C1
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;
}

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

0 赞同 0 条回复

小吕普通 2023年6月21日下午2:33

cpp,不会，看的题解
unordered_map<Node,Node>cacheNode;
Node* copyRandomList(Node* head) {
if(headNULL)
{
return head;
}
if(!cacheNode.count(head))
{
Node* headNew = new Node(head->val);
cacheNode[head] = headNew;
headNew->next = copyRandomList(head->next);
headNew->random = copyRandomList(head->random);
}
return cacheNode[head];
}

0 赞同 0 条回复

zll 普通 2023年6月21日下午2:29

“`c++
/*
// 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* 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;
}

// 拆分,比如把 A->A1->B->B1->C->C1拆分成 A->B->C和A1->B1->C1
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 条回复

跋扈疙瘩汤普通 2023年6月21日下午12:30

用哈希来实现的，空间复杂度相对于原地复制要高，但是好理解
1、在遍历原链表的同时创建对应的新节点插入哈希表进行匹配；
2、遍历完成后哈希表中原链表节点映射的新节点串联起来；
3、最后返回哈希表中存储的原链表的头节点

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) return head;
        Node* newHead = head;
        unordered_map<Node*, Node*> mp;
        while (newHead) {
            mp[newHead] = new Node(newHead->val);
            newHead = newHead->next;
        }
        newHead = head;
        while (newHead) {
            mp[newHead]->next = mp[newHead->next];
            mp[newHead]->random = mp[newHead->random];
            newHead = newHead->next;
        }
        return mp[head];
    }
};

0 赞同 0 条回复

悠若普通 2023年6月21日上午11:23

复制并拆分

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

名字什么的好麻烦普通 2023年6月21日上午11:16

哈希

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

mpweixin用户普通 2023年6月21日上午9:46

C++
两个解法，第一个较为方便，但是O(n)空间，第二个O(1)空间

解法1: 使用hashMap，先复制所有的节点，再复制所有节点的next和random
TC: O(n)
SC: O(n)

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

解法2: 先复制所有节点，把每个复制的节点接在每个原来节点的后面。完成后，复制所有的random。再将原来的和复制的拆开。
TC: O(n)
SC: O(1)
```C++
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) {
            return NULL;
        }
        Node* curr = head;
        Node* copy_curr = NULL;
        Node* copy_head = NULL;
        while (curr) {
            copy_curr = new Node(curr->val, curr->next, NULL);
            curr->next = copy_curr;
            curr = copy_curr->next;
        }
        curr = head;
        while (curr) {
            copy_curr = curr->next;
            if (curr->random) {
                copy_curr->random = curr->random->next;
            }
            curr = copy_curr->next;
        }
        curr = head;
        copy_head = curr->next;
        while (curr) {
            copy_curr = curr->next;
            curr->next = copy_curr->next;
            curr = curr->next;
            if (curr) {
                copy_curr->next = curr->next;
            }
        }
        return copy_head;
    }
};

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年6月21日上午9:36

"""
# 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

        # 复制&合并
        cur = head
        while cur:
            nxt = cur.next
            cur.next = Node(cur.val)
            cur.next.next = nxt
            cur = nxt

        # 复制random node
        cur = head
        while cur:
            new_cur = cur.next
            new_cur.random = cur.random.next if cur.random else None
            cur = cur.next.next

        # 拆分
        res = head.next
        cur = head
        new_cur = head.next
        while cur:
            nxt = cur.next
            cur.next = cur.next.next
            cur = cur.next
            new_cur.next = cur.next if cur else None
            new_cur = new_cur.next

        return res

0 赞同 0 条回复

花老爷普通 2023年6月21日上午9:07

遍历+map：两次遍历，第一次遍历创建链表所有节点，并且把新链表与旧链表的每个节点用map对应起来；第二次遍历依靠map创建新链表中每个节点的random。
时间：O(n)
空间：O(n)

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

0 赞同 0 条回复

局外人普通 2023年6月21日上午9:07

思路：遍历链表，依次生成节点嵌入哈希表中，然后再次遍历，生成各个节点间的链接
时间复杂度：O(n), 空间复杂度O(n)

class Solution {
public:
    Node* copyRandomList(Node* head) {
        unordered_map<Node*, Node*> hash;
        Node *p=head;
        while(p!=NULL){
            if(hash.find(p)<span class="text-highlighted-inline" style="background-color: #fffd38;">hash.end())
                hash[p]=new Node(p->val);
            p=p->next;
        }</span>

<pre><code>    Node *q=head;
    while(q!=NULL){
        if(q->next!=NULL)   hash[q]->next=hash[q->next];
        if(q->random!=NULL) hash[q]->random=hash[q->random];
        q=q->next;
    }
    return hash[head];
}
</code></pre>

};

0 赞同 0 条回复

　　　　　　　　普通 2023年6月21日上午3:15

class Solution {
public:
    Node* copyRandomList(Node* head) {
        unordered_map<Node*,Node*>m;
        Node* res=new Node(0),*cur=res,*p=head,*q=res;
        while(head){
            Node* t=new Node(head->val);
            cur->next=t;
            cur=t;
            m[head]=cur;
            head=head->next;
        }
        q=q->next;
        while(p){
            q->random=m[p->random];
            p=p->next;
            q=q->next;
        }
        return res->next;
    }
};

【时间O(n),空间O(n)】
先复制next指针，同时存储两个链表节点的对应关系
然后复制rand指针

0 赞同 0 条回复

大鑫啊普通 2023年6月21日上午12:47

时间复杂度：O(n)
空间复杂度：O(1)
1、判空，复制链表节点
2、复制随机节点
3、拆分,比如把 A->A1->B->B1->C->C1拆分成 A->B->C和A1->B1->C1

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

0 赞同 0 条回复

硬核洋葱普通 2023年6月20日下午11:14

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

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        Node* p = head;
        Node* dummyhead = new Node(-1), *pnew = dummyhead;
        unordered_map<Node*, Node*> mapping;

        while(p){
            Node* newnode = new Node(p->val);
            pnew->next = newnode;
            pnew = newnode;
            mapping[p] = pnew;
            p = p->next;
        }
        mapping[NULL] = NULL;

        pnew = dummyhead->next;
        p = head;
        while(p){
            pnew->random = mapping[p->random];
            pnew = pnew->next;
            p = p->next;
        }
        return dummyhead->next;
    }
};

时间复杂度 O(n) 空间复杂度 O(n)
首先必须做两遍遍历，因为第一遍的时候random所指节点可能还没有建出来。第一遍遍历能填充全部的 val 和 next
第二遍遍历的时候填充random，参考p的random指针，所以在这之前可以建立一个新链表和旧链表之间节点的对应

0 赞同 0 条回复

怀瑾永久会员 2023年6月20日下午11:04

思路：
首先是复制节点，然后复制节点的random指针（将原节点的random指针指向的节点的下一个节点赋值给原节点的下一个节点（复制节点）的random指针），后将链表拆分，返回深拷贝后的头指针即可。

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

0 赞同 0 条回复

yxy 普通 2023年6月20日下午10: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) return nullptr;
        unordered_map<Node*, Node*> um;
        Node* cur = head;
        while(cur)
        {
            Node* tmp = new Node(cur->val);
            um[cur]=tmp;
            cur=cur->next;
        }
        cur = head;
        while(cur)
        {
            Node* tmp = um[cur];
            tmp->next = um[cur->next];
            tmp->random = um[cur->random];
            cur=cur->next;
        }
        return um[head];
    }
};

0 赞同 0 条回复

拾陆. 普通 2023年6月20日下午10:41

/*
// 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* cur = head;
        while(cur){
            Node* node = cur->next;
            cur->next = new Node(cur->val);
            cur->next->next = node;
            cur = node;
        }

        cur = head;
        while(cur){
            Node* node = cur->next;
            node->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 条回复

～普通 2023年6月20日下午10:37

哈希映射
class Solution {
public:
Node* copyRandomList(Node* head) {
if (head nullptr) return nullptr;

std::unordered_map<Node*, Node*> nodeMap; // 用于存储原节点和复制节点的对应关系

Node* curr = head;
Node* newList = new Node(curr->val); // 复制头节点
nodeMap[curr] = newList;

while (curr != nullptr) {
    Node* clone = nodeMap[curr];

    if (curr->next) {
        if (nodeMap.find(curr->next) == nodeMap.end()) {
            // 若当前节点的下一个节点还未被复制，则先创建新节点，并建立映射关系
            nodeMap[curr->next] = new Node(curr->next->val);
        }
        clone->next = nodeMap[curr->next]; // 设置复制节点的next指针
    }

    if (curr->random) {
        if (nodeMap.find(curr->random) == nodeMap.end()) {
            // 若当前节点的随机节点还未被复制，则先创建新节点，并建立映射关系
            nodeMap[curr->random] = new Node(curr->random->val);
        }
        clone->random = nodeMap[curr->random]; // 设置复制节点的random指针
    }

    curr = curr->next;
}

return nodeMap[head];

}
};

0 赞同 0 条回复

张君雅小妹妹普通 2023年6月20日下午10:28

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

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        Node cur = head;
        // 复制next
        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 random = cur.random;
            cur.next.random = random == null ? null : random.next;
            cur = cur.next.next;
        }
        // 分离
        cur = head;
        Node curNew = head.next;
        Node headNew = curNew;
        while(cur != null) {
            cur.next = cur.next.next;
            curNew.next = cur.next == null ? null : cur.next.next;
            cur = cur.next;
            curNew = curNew.next;
        }

        return headNew;        
    }
}

0 赞同 0 条回复

désire. 普通 2023年6月20日下午10:24

C++:复制加拆分（第一次接触
class Solution {
public:
Node* copyRandomList(Node* head) {
if(head NULL) return head;
Node* cur = head;
//复制节点
while(cur){
Node* next = cur->next;
cur->next = new Node(cur->val);
cur->next->next = next;
cur = next;
}
//复制随机节点
cur = head;
while(cur){
//Node* curNew = cur->next;
//curNew->random = cur->random NULL ? NULL : cur->random->next;
cur->next->random = cur->random NULL ? NULL : cur->random->next;
cur = cur->next->next;
}
//拆分节点
Node* headnew = head->next;
cur = head;
Node* curnew = cur->next;
while(cur){
cur->next = cur->next->next;
cur = cur->next;
curnew->next = cur NULL ? NULL : cur->next;
curnew = curnew->next;
}
return headnew;

};

0 赞同 0 条回复

江畅普通 2023年6月20日下午10:22

class Solution {
public:
    // 时间复杂度 O(N)
    // 空间复杂度 O(1)
    Node* copyRandomList(Node* head) {
        if (head == nullptr) return head;

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

        // 复制 random 指向
        cur = head;
        while (cur != nullptr) {
            if (cur->random != nullptr) {
                cur->next->random = cur->random->next;
            }
            cur = cur->next->next;
        }

        // 拆分
        Node* ori = head;
        Node* res = head->next;
        cur = head->next;  // 以复制的链表节点用于判断链表尾
        while (cur->next != nullptr) {
            ori->next = ori->next->next;
            cur->next = cur->next->next;
            ori = ori->next;
            cur = cur->next;
        }

        ori->next = nullptr;

        return res;
    }
};

0 赞同 0 条回复

伏月三十普通 2023年6月20日下午10:13

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

    //复制next指针
    Node cur=head;
    while(cur!=null){
        //复制之前先把后续节点保留下来
        Node temp=cur.next; //A的后续节点就是B
        cur.next=new Node(cur.val);
        cur.next.next=temp;
        cur=temp; //上面保存下来 直接就到B了
    }

    //复制random指针
    cur=head;//把指针再拉到头节点
    while(cur!=null){
        Node curNew=cur.next; //求A1的random
        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;//需要返回的链表  从A1开始的  指向的是复制链表的头指针
    cur=head;
    Node curNew=head.next;
    while(cur != null){
        cur.next=cur.next.next; //A->B
        cur=cur.next; //cur指向B
        curNew.next=cur==null?null:cur.next; //A1->B1
        curNew=curNew.next;
    }
    return headNew;
}

}

0 赞同 0 条回复

jhfuture 普通 2023年6月20日下午9:55

java实现

/*
// 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;
        //1.复制顺序结点
        Node tmp=head;
        while(tmp!=null){
            Node newNode=new Node(tmp.val);
            newNode.next=tmp.next;
            tmp.next=newNode;
            tmp=newNode.next;
    }
    //2.复制随机指针，因为复制后的结点，指针还是没有指向正确的位置
    tmp=head;
    while(tmp!=null){
        Node copeNode=tmp.next;
        copeNode.random=tmp.random==null?null:tmp.random.next;
        tmp=copeNode.next;

    }
    //3.拆分，并返回复制的
    Node copy=head.next;
    Node copyTmp=copy;
    tmp=head;
    while(tmp!=null){
        tmp.next=tmp.next.next;
        tmp=tmp.next;
        copyTmp.next=tmp==null?null:tmp.next;
        copyTmp=copyTmp.next;
    }
    return copy;

    }
}

只能说理解起来不难，但太容易出错了！

0 赞同 0 条回复

Vow the vow。普通 2023年6月20日下午9:46

原地反转还是好难理解……

// 法一：模拟+哈希表
    // public Node copyRandomList(Node head) {
    //     Node dummyNode = new Node(-10001);
    //     Node cur = dummyNode;
    //     Node dummyHead = head;
    //     HashMap<Node,Node> map = new HashMap<>();
    //     // 先复制next指针
    //     while(head != null){
    //         Node node = new Node(head.val);
    //         cur.next = node;
    //         map.put(head,node);
    //         cur = cur.next;
    //         head = head.next;
    //     }
    //     // 再复制random指针，难点是random指针必须是新链表的node
    //     cur = dummyNode.next;
    //     head = dummyHead;
    //     while(head != null){
    //         if(head.random != null){
    //             cur.random = map.get(head.random);
    //         }
    //         cur = cur.next;
    //         head = head.next;
    //     }
    //     return dummyNode.next;

    // }

    // 法二：模拟+原地复制
    public Node copyRandomList(Node head) {
        if(head == null) return head;

        Node dummyHead = new Node(-10001);
        dummyHead.next = head;
        // 复制一份节点
        while(head != null){
            Node node = new Node(head.val);
            node.next = head.next;
            head.next = node;
            head = node.next;
        }
        // 偶数位置的节点为新节点，奇偶位置的节点有映射关系map
        head = dummyHead.next;
        while(head != null){
            if(head.random != null){
                head.next.random = head.random.next;
            }
            head = head.next.next;
        }
        // 删除奇数位置的节点-》链表拆分
        head = dummyHead.next;
        Node newHead = head.next;
        while(head != null){
            Node ne = head.next;
            if(ne != null) head.next = ne.next; // 
            head = ne;  // 一下处理一个节点，奇偶数位置的节点的操作是一样

        }
        return newHead;
    }

0 赞同 0 条回复

Ming 普通 2023年6月20日下午9:40

这里是Ming的打卡：
多多注意空指针情况，考虑随机结点是否为空再去走下一步

/*
// 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) {
            //先得到B，在建立A1，改变指向A->A1->B
            Node next = cur.next;
            cur.next = new Node(cur.val);
            cur.next.next = next;
            cur = next;
        }
        //复制随机结点
        cur = head;
        while(cur != null) {
            //使A1->C1，随机结点相互连接
            Node curNew = cur.next;
            //注意空节点
            curNew.random = cur.random == null ? null : cur.random.next;
            cur = cur.next.next;
        }
        //拆分成A->B->C 和 A1->B1->C1
        Node newNode = head.next;
        cur = head;
        Node curNew = newNode;
        while(cur != null) {
            //先A->B,再cur=B,A1.next = cur.next 也就是A1->B1反复
            cur.next = cur.next.next;
            cur = cur.next;
            curNew.next = cur == null ? null : cur.next;
            curNew = curNew.next;
        }
        return newNode;
    }
}

0 赞同 0 条回复

* 普通 2023年6月20日下午9:39

js实现
var copyRandomList = function(head) {
if(head=null){
return null;
}
let cur=head;
let map=new Map();
while(cur!null){
map.set(cur,new Node(cur.val,null,null));
cur=cur.next;
}
cur=head;
while(cur!null){
map.get(cur).next=map.get(cur.next)??null;
map.get(cur).random=map.get(cur.random)?? map.get(cur.random);
cur=cur.next;
}
return map.get(head);
};

0 赞同 0 条回复

mpweixin用户永久会员 2023年6月20日下午8:41

//时间O(n)，空间O(1)
public Node copyRandomList(Node head) {
    if(head == null){
        return head;
    }

    //复制
    Node cur = head;
    while(cur != null){
        Node copyNode = new Node(cur.val);
        copyNode.next = cur.next;
        cur.next = copyNode;
        cur = cur.next.next;
    }

    //维护random指针
    cur = head;
    while(cur != null){
        if(cur.random == null){
            cur.next.random = null;
        }else{
            cur.next.random = cur.random.next;
        }
        cur = cur.next.next;
    }

    //拆分
    Node copyHead = head.next;  //  记录copy后的头结点
    cur = head;
    Node curCopy = copyHead;
    while(cur != null){
        cur.next = cur.next.next;
        cur = cur.next;

        curCopy.next = curCopy.next == null?null:curCopy.next.next;
        curCopy = curCopy.next;
    }

    return copyHead;
}

0 赞同 0 条回复

行动派小彩笔普通 2023年6月20日下午8:24

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

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
// // 拼接、拆分 时间O(n)，空间O(1),根据题目要求，没有多出来的空间
// 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)
//         {
//           Node* tmp = cur->next;
//           tmp->random = cur->random!=NULL? cur->random->next:NULL;
//           cur = cur->next->next;
//         }
//         cur = head;
//         Node* last = cur->next;
//         Node* ans = last;
//         while(cur!=NULL)
//         {
//             cur->next = cur->next->next;
//             if(last->next!=NULL)
//                 last->next = last->next->next;
//             cur = cur->next;
//             last = last->next;
//         }
//         return ans;
//     }
// };
// 哈希表，时间O(n)，空间O(n) 有额外空间
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head == NULL) return head;
     unordered_map<Node*,Node*> mp;
     Node* cur = head;
     while(cur!=NULL)
     {
         mp[cur] = new Node(cur->val);
         cur = cur->next;

     }
    cur = head;
     while(cur!=NULL)
     {
         mp[cur]->next = mp[cur->next];
         mp[cur]->random = mp[cur->random];
         cur = cur->next;
     }
     return mp[head];
    }
};

1 赞同 0 条回复

mpweixin用户普通 2023年6月20日下午8:14

思路：
1、复制节点的值，将新复制的节点的值直接放在原有节点的后面
2、复制random指针部分，由于新复制的节点在原来节点的后面，那么复制后的random指针所指的就是原来random指针所指的后一个节点。
3、拆分链表

“`c++
class Solution {
public:
Node* copyRandomList(Node* head) {
if(!head){
return NULL;
}
// 1、复制节点的值，将新复制的节点的值直接放在原有节点的后面
Node* cur = head;
while(cur){
Node* newcur = new Node(0);
newcur->val = cur->val;
newcur->next = cur->next;
cur->next = newcur;
cur = newcur->next;
}
// 2、复制random指针部分
cur = head;
while(cur){
if(cur->random){
cur->next->random = cur->random->next;
}
cur = cur->next->next;
}
// 3、拆分链表
cur = head;
Node* newHead = head->next; // 记录拆分后的复制出来的新链表的头指针
Node* temp = nullptr;
while(cur->next){
temp = cur->next;
cur->next = temp->next;
cur = temp;
}
return newHead;
}
};

0 赞同 0 条回复

peach 普通 2023年6月20日下午7:55

思路

这道题想复杂了
给出一个map，key是原来的node，value是复制后的node
先遍历一次链表，把node复制之后，放到map中
再遍历一次链表，处理next指针和random指针

代码

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

雨落圆荷普通 2023年6月20日下午5:20

class Solution{
public Node copyRamdomList(Node head){
if(headnull){
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.randomnull?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;
}
}
时间复杂度：O(n)
额外空间复杂度：O(1)

0 赞同 0 条回复

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

共以下 62 个回答

代码

思路

代码

# 回答此问题取消回复

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

共以下 62 个回答

代码

思路

代码

# 回答此问题 取消回复

# 回答此问题取消回复