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

mpweixin用户普通 2023年8月4日下午1:37

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

/*
// 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) {
        //输入判空，重要，而且会影响下面headNew=head->next的代码
        if(head==nullptr){
            return head;
        }
        //此处将新结点一个个插入
        for(Node* node=head;node!=nullptr;node=node->next->next){
            Node* nodeNew=new Node(node->val);
            nodeNew->next=node->next;
            node->next=nodeNew;
        }

        //此处复制原表中的random指针
        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年7月26日下午9:04

一种hashmap 一种聚合拆分，关键点找到新链表的random，只能通过旧链表来找。拆分时注意最后结点的拆分

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

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

}
*/
// class Solution {
// public Node copyRandomList(Node head) {
// if(headnull){
// return null;
// }
// Map<Node,Node> map=new HashMap();
// Node cur=head;
// while(cur!=null){
// Node temp=new Node(cur.val);
// map.put(cur,temp);
// 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);

// }
// }

class Solution {
public Node copyRandomList(Node head) {
if(headnull){
return null;
}
Node cur=head;
while(cur!=null){
Node temp=new Node(cur.val);
temp.next=cur.next;
cur.next=temp;
cur=temp.next;
}

    cur=head;
    while(cur!=null){
        if(cur.random!=null){
            cur.next.random=cur.random.next;

        }
        cur=cur.next.next;
    }
    cur=head.next;
    Node res=head.next;
    Node pre=head;
    while(cur.next!=null){
        pre.next=pre.next.next;
        cur.next=cur.next.next;
        cur=cur.next;
        pre=pre.next;
    }
    pre.next=null;
    return res;

}

}

0 赞同 0 条回复

望仔普通 2023年7月26日下午8:55

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

    // 第一次遍历，先记录当前节点与新节点的映射关系
    m := make(map[*Node]*Node)
    for cur := head; cur != nil; cur = cur.Next {
        m[cur] = &Node{Val: cur.Val}
    }

    // 第二次遍历，给新节点加上需要指向的rand节点，并且把新节点串联起来
    for cur := head; cur != nil; cur = cur.Next {
        m[cur].Next = m[cur.Next]
        m[cur].Random = m[cur.Random]
    }

    return m[head]
}

0 赞同 0 条回复

李敏普通 2023年7月22日下午1:25

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        Node cur = head;
        Map<Node, Node> map = new HashMap<>();
        // 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
        while(cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        // 4. 构建新链表的 next 和 random 指向
        while(cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        // 5. 返回新链表的头节点
        return map.get(head);
    }
}

0 赞同 0 条回复

hi 普通 2023年7月22日上午9:56

先判断链表为空的特殊情况、
再根据next 指针复制节点
复制节点的random 指针
注意代码中指针所指节点为空的情况

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

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        //判断特殊情况
        if(head == NULL) return NULL;

        //根据next 指针复制节点
        Node* cur = head;
        while(cur)
        {
            Node* np = new Node(cur -> val);
            Node* next = cur -> next;
            cur -> next = np;
            np -> next = next;
            cur = next;
        }

        //完善节点的Random 指针
        cur = head;
        while(cur)
        {
            cur -> next -> random = cur -> random == NULL ? NULL : cur -> random -> next;
            cur = cur -> next -> next;
        } 

        //拆分链表 A->A1->B->B1->C->C1 为A->B->C 和A1->B1->C1
        cur = head;
        Node* headNew = head -> next;
        Node* curNew = head -> 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 条回复

wowo 普通 2023年7月20日上午2:15

迭代，先复制节点，再拆分
O（n), O(1)

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return None

        cur = head
        # copy
        while (cur):
            nextcur = cur.next
            cur.next = Node(cur.val)
            cur.next.next = nextcur
            cur = cur.next.next

        cur = head
        # copy random
        while (cur):
            if (cur.random):
                cur.next.random = cur.random.next
            else:
                cur.next.random = None
            cur = cur.next.next

        cur = head
        newhead = head.next
        # delete
        while (cur):
            newcur = cur.next
            cur.next = cur.next.next # already link A and B

            if (newcur.next):
                newcur.next = newcur.next.next
            else:
                newcur.next = None

            cur = cur.next # not cur.next.next

        return newhead

0 赞同 0 条回复

新禾普通 2023年7月16日下午4:21

// 时间复杂度on 空间复杂度on 构建原链表节点和新链表对应节点的键值对映射关系，再遍历构建新链表各节点的 next 和 random 引用指向
class Solution {
public Node copyRandomList(Node head) {
if(head null) return null;
Node cur = head;
Map<Node, Node> map = new HashMap<>();

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

    cur = head;

    while(cur != null) {
    map.get(cur).next = map.get(cur.next);
    map.get(cur).random = map.get(cur.random);
    cur = cur.next;
    }
  return map.get(head);
}

}

0 赞同 0 条回复

Edenms-u 普通 2023年7月15日上午11:29

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

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head == NULL)
            return head;
        Node* nhead = head;
        while(nhead != NULL){
            Node* tmp = new Node(nhead->val);
            tmp->next = nhead->next;
            nhead->next = tmp;
            nhead = tmp->next;
        }
        nhead = head;
        while(nhead != NULL){
            if(nhead->random != NULL)
                nhead->next->random = nhead->random->next;
            nhead = nhead->next->next;
        }
        nhead = head->next;
        Node* ahead = head, * bhead = head->next;
        while(bhead->next != NULL){
            ahead->next = bhead->next;
            ahead = ahead->next;
            bhead->next = ahead->next;
            bhead = bhead->next;
        }
        ahead->next = NULL;

        return nhead;
    }
};

一直没想明白原来要新建个链表😂

0 赞同 0 条回复

mpweixin用户普通 2023年7月13日下午12:29

太难了拆分-重组方法

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head == nullptr) return nullptr;
        Node* cur = head;
        // 1. 复制各节点，并构建拼接链表
        while(cur != nullptr) {
            Node* tmp = new Node(cur->val);
            tmp->next = cur->next;
            cur->next = tmp;
            cur = tmp->next;
        }
        // 2. 构建各新节点的 random 指向
        cur = head;
        while(cur != nullptr) {
            if(cur->random != nullptr)
                cur->next->random = cur->random->next;
            cur = cur->next->next;
        }
        // 3. 拆分两链表
        cur = head->next;
        Node* pre = head, *res = head->next;
        while(cur->next != nullptr) {
            pre->next = pre->next->next;
            cur->next = cur->next->next;
            pre = pre->next;
            cur = cur->next;
        }
        pre->next = nullptr; // 单独处理原链表尾节点
        return res;      // 返回新链表头节点
    }
};

0 赞同 0 条回复

momo 普通 2023年7月12日上午10:39

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

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

0 赞同 0 条回复

finalrgy 普通 2023年7月11日下午10:37

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

    virtualHead := &Node{}
    cur, cur1 := head, virtualHead

    var nodeList1 []*Node
    var cnt int
    nodeMap := make(map[*Node]int)

    for cur != nil {
        cur1.Next = &Node{Val: cur.Val}
        nodeList1 = append(nodeList1, cur1.Next)
        nodeMap[cur] = cnt

        cnt += 1
        cur = cur.Next
        cur1 = cur1.Next
    }

    cur, cur1 = head, virtualHead.Next
    for cur != nil {
        if index, ok := nodeMap[cur.Random]; ok {
            cur1.Random = nodeList1[index]
        }
        cur = cur.Next
        cur1 = cur1.Next
    }

    return virtualHead.Next
}

思路：用map记录每个结点的下标，随机结点的下标位置和复制的链表相同
时间复杂度O(N)，空间复杂度O(N)

空间复杂度还可以优化成O(1)

0 赞同 0 条回复

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

class Solution {
    //之前没做过, 思路:复制+拆分
public:
    Node* copyRandomList(Node* head) {
        if(!head){
            return nullptr;
        }
        Node* p = head;
        //复制
        while(p){
            Node* tmp = new Node(p->val);
            tmp->next = p->next;
            p->next = tmp;
            p = tmp->next;
        }
        p = head;
        while(p){
            if(p->random)
                p->next->random = p->random->next;
            else
                p->next->random = nullptr;
            p = p->next->next;
        }

        // 拆分
        Node* newHead = head->next;
        p = head;
        Node* q = newHead;
        while(q->next){
            p->next = q->next;
            p = p->next;
            q->next = p->next;
            q = q->next;
        }
        p->next = nullptr;
        q->next = nullptr;
        return newHead;
    }
};

0 赞同 0 条回复

NullPointerException 普通 2023年7月11日下午4:18

public Node copyRandomList(Node head) {
if(headnull)
{
return null;
}
//难点在复制的时候 romdom的指向因为后面还没创建
HashMap<Node,Node> map=new HashMap<Node,Node>();
Node cur;
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年7月11日下午12:14

迭代
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head<span class="text-highlighted-inline" style="background-color: #fffd38;">nullptr) return nullptr;</span>

<pre><code>    Node* cur=head;
    while(cur!=nullptr){
        Node* tmp=new Node(cur->val);
        tmp->next=cur->next;
        cur->next=tmp;
        cur=cur->next->next;
    }

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

    Node* ans=head->next;
    cur=head;
    Node* tmp2=head->next;
    while(cur!=nullptr){
        cur->next=cur->next->next;
        cur=cur->next;
        if(tmp2->next!=nullptr){
            tmp2->next=tmp2->next->next;
            tmp2=tmp2->next;
        }
    }

    return ans;
}
</code></pre>

};

0 赞同 0 条回复

周小二普通 2023年7月10日下午10:41

class Solution {
    //递归
    // Map<Node, Node> cacheNode = new HashMap<>();
    // public Node copyRandomList(Node head) {
    //     if (head == null) {
    //         return null;
    //     }
    //     if (!cacheNode.containsKey(head)) {
    //         Node copyNode = new Node(head.val);
    //         cacheNode.put(head, copyNode);
    //         copyNode.next = copyRandomList(head.next);
    //         copyNode.random = copyRandomList(head.random);
    //     }
    //     return cacheNode.get(head);
    // }

    //迭代

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        for(Node node = head; node != null; node = node.next.next) {
            Node copyNode = new Node(node.val);
            copyNode.next = node.next;
            node.next = copyNode;
        }
        for(Node node = head; node != null; node = node.next.next) {
            Node copyNode = node.next;
            copyNode.random = node.random != null ? node.random.next : null;
        }
        Node copyNodeHead = head.next;
        for(Node node = head; node != null; node = node.next) {
            Node copyNode = node.next;
            node.next = node.next.next;
            copyNode.next = copyNode.next != null ? copyNode.next.next : null;
        }
        return copyNodeHead;
    }
}

0 赞同 0 条回复

doordie. 普通 2023年7月10日下午5:24

哈希表

 // 如果head为null，直接返回null
        if (head == null) {
            return null;
        }
        // 建立哈希表
        Node cur = head;
        // key:原链表节点你 val:新链表节点
        HashMap<Node,Node> dic = new HashMap<>();
        // 复制链表 存储在哈希表
        while (cur != null){
             dic.put(cur,new Node(cur.val));
             cur = cur.next;
        }
        cur = head;
        // 构建新链表的引用指向
        while (cur != null){
            dic.get(cur).next = dic.get(cur.next);
            dic.get(cur).random = dic.get(cur.random);
            cur = cur.next;
        }
        //返回新链表的头节点
        return dic.get(head);

0 赞同 0 条回复

刹那芳间普通 2023年7月10日下午2:24

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

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

        return headNew;
    }
}

0 赞同 0 条回复

V2ero 普通 2023年7月10日下午1:29

var copyRandomList = function(head) {
    if(!head) {
        return null
    }
    const map = new Map();
    let cur = head;
    // 第一次遍历,映射旧链表与新节点的关系
    while(cur){
        const node = new Node(cur.val);
        map.set(cur, node);
        cur =  cur.next;
    }

    map.set(null, null); // 补充空节点映射

    cur =  head;

    // 第二次遍历完成对应的next与random
    while(cur){
       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年7月10日上午12:25

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

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
        if(head == null){
            return head;
        }
        //复制链表节点
        Node cur = head;
        while(cur != null){
            Node 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 条回复

ppopp 普通 2023年7月10日上午12:23

class Solution {
public:
Node* copyRandomList(Node* head) {
//边界条件：head判空
if(head nullptr) return nullptr;
Node* p = head;
unordered_map<Node*, Node*> map;

    //copy each node, and build up hash-map
    while(p != nullptr){
        map[p] = new Node(p->val);//attention! this is an intact node
        p = p->next;
    }
    //p return to head
    p = head;
    //build up new linklist's next and random
    while(p != nullptr){
        map[p] -> next = map[p -> next];
        map[p] -> random = map[p -> random];
        p = p->next;
    }        
    return map[head];
}

};

0 赞同 0 条回复

CKX 普通 2023年7月10日上午12:13

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

    //复制
    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 {
            curNew.Random = nil
        } else {
            curNew.Random = cur.Random.Next
        }

        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
}

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

0 赞同 0 条回复

Terence💧 普通 2023年7月9日下午11:54

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Next *Node
 *     Random *Node
 * }
 */

func copyRandomList(head *Node) *Node {
    hash := make(map[*Node]*Node)
    for tmp := head; tmp != nil; tmp = tmp.Next {
        hash[tmp] = &Node{Val: tmp.Val, Next: nil, Random: nil,}
    }

    for tmp := head; tmp != nil; tmp = tmp.Next {
        tmpNew := hash[tmp]
        tmpNew.Next, tmpNew.Random = hash[tmp.Next], hash[tmp.Random]
    }
    return hash[head]
}

时间复杂度On

0 赞同 0 条回复

mpweixin用户普通 2023年7月9日下午11:02

public Node copyRandomList(Node head) {
if (head null) {
return head;
}
//将拷贝节点放到原节点后面，例如1->2->3这样的链表就变成了这样1->1′->2->2′->3->3′
for (Node node = head, copy = null; node != null; node = node.next.next) {
copy = new Node(node.val);
copy.next = node.next;
node.next = copy;
}
//把拷贝节点的random指针安排上
for (Node node = head; node != null; node = node.next.next) {
if (node.random != null) {
node.next.random = node.random.next;
}
}
//分离拷贝节点和原节点，变成1->2->3和1′->2′->3’两个链表，后者就是答案
Node newHead = head.next;
for (Node node = head, temp = null; node != null && node.next != null;) {
temp = node.next;
node.next = temp.next;
node = temp;
}

    return newHead;
}

时间复杂度空间复杂度都为O（n）

0 赞同 0 条回复

Fighting boy😀 普通 2023年7月9日下午9:54

/*
// 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月9日下午9:01

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

“`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= = NULL) return NULL;
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 *New= cur ->next;
New ->random =cur->random = =NULL ? NULL: cur->random->next;
cur=cur->next->next;
}
Node *heNew=head->next;
Node *New=head->next;
cur=head;
while(cur)
{
cur->next = cur ->next ->next;
cur =cur->next;
New->next =cur= = NULL ? NULL : cur->next;
New = New->next;
}
return heNew;
}
};

0 赞同 0 条回复

KCOcean 普通 2023年7月9日下午6:53

代码

 Node* copyRandomList(Node* head) {
        if(!head) return head;
        Node *cur = head;
        while(cur){
            Node *nodeSaved = cur->next;
            cur->next = new Node(cur->val);
            cur->next->next = nodeSaved;
            cur = nodeSaved;
        }
        cur = head;
        while(cur){
            Node * curNew = cur->next;
            curNew->random = cur->random ? cur->random->next : nullptr;
            cur = cur->next->next;
        }
        cur = head;
        Node *headNew = head->next;
        Node *curNew = headNew;
        while(cur){
            cur->next = cur->next->next;
            cur = cur->next;
            curNew->next = cur ? cur->next : nullptr;
            curNew = curNew->next;
        }

        return headNew;
    }

0 赞同 0 条回复

Mooby 普通 2023年7月9日下午6:27

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

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

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

0 赞同 0 条回复

3A87 普通 2023年7月9日下午6:17

/*
// 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后面的节点
            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;//把A1分走
            cur=cur->next;//到B
            curNew->next=cur ? cur->next : nullptr; //分走B1
            curNew=curNew->next;//移动，指向B1
        }
        return headNew;

    }
};

0 赞同 0 条回复

人生何处不青山普通 2023年7月9日下午5:08

也就我用TS写了

/**
 * // 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) return head;
    let cur = head;
    while (cur) {
        let t = cur.next;
        cur.next = new Node(cur.val, cur.next, null);
        cur = t;
    }
    // 复制完节点
    cur = head;
    while (cur) {
        cur.next.random = cur.random ? cur.random.next : null;
        cur = cur.next.next;
    }
    // 赋值随机节点,开始恢复原样
    cur = head;
    let copyNode = head.next;
    let res = copyNode;
    while (copyNode.next) {
        cur.next = copyNode.next;
        copyNode.next = copyNode.next.next;
        cur = cur.next;
        copyNode = copyNode.next;
    }
    cur.next = null; // 一直循环到了最后一个复制节点，这时候cur指向最后一个原节点，应该next为null
    return res;
};

0 赞同 0 条回复

片言莫语普通 2023年7月9日下午5:01

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

T(n) = O(n） S(n)=O（n）

0 赞同 0 条回复

AD钙奶普通 2023年7月9日下午3:21

思路：
1. 使用哈希表建立旧节点与新节点的映射关系。
2. 遍历链表，将新节点进行连接。

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,null,null));
            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)

0 赞同 0 条回复

Mr.Man 普通 2023年7月9日下午3:12

class Solution {
    public Node copyRandomList(Node head) {
        if(head==null) return head;
        Node cur=head;
        while(cur!=null){
            Node newNode=new Node(cur.val);
            newNode.next=cur.next;
            cur.next=newNode;
            cur=newNode.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 条回复

June 普通 2023年7月9日上午11:41

/*
// 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) {

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

        if( head == null)
            return null;
        Node newHead = new Node(head.val);
        Node p2 = newHead;
        Node p1 = head.next;
        nodeMap.put(head,newHead);
        while(p1 != null)
        {
            Node nextNode = new Node(p1.val,p1.next,null);
            p2.next = nextNode;
            nodeMap.put(p1,nextNode);
            p1 = p1.next;
            p2 = p2.next;
        }
        p1 = head;
        p2 = newHead;
        while(p1 != null) // 处理 random的
        {
            p2.random = nodeMap.get(p1.random);
            p1 = p1.next;
            p2 = p2.next;
        }

        return newHead;
    }
}

0 赞同 0 条回复

枫梓。普通 2023年7月9日上午10:29

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head) return NULL;
        Node *cur = head;
        while(cur) {
            Node *tmp = new Node(cur->val);
            Node *next = cur->next;
            cur->next = tmp;
            tmp->next = next;
            cur = next;
        }
        cur = head;
        Node *newhead = cur->next;
        //random指向的copy
        while(cur) {
            // cur->next 为cur的拷贝结点
            Node *next = cur->next->next;
            Node *copy = cur->next;
            copy->random = cur->random? cur->random->next:nullptr;
            cur = next;
        }
        cur = head;
        //next指向的copy
        while(cur) {
            Node *next = cur->next->next;
            Node *copy = cur->next;
            copy->next = next? next->next : nullptr;
            cur->next = next ? next : nullptr;
            cur = next;
        }
        return newhead;
    }
};

复杂链表的复制。思路，遍历拷贝链表中每一个结点，拷贝插入到该节点之后。然后遍历一次复制出random指向的信息，遍历第二次复制出next指向的信息。时间 O(n), 空间O(1)。

0 赞同 0 条回复

朱志刚普通 2023年7月8日下午11:14

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

    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* newhead = cur->next;
        newhead->random = cur->random ? cur->random->next : NULL;
        cur = cur->next->next;
    }

    Node* headNew = head->next;
    cur = head;
    Node* curNew = head->next;
    while (cur) {
        cur->next = cur->next->next;
        cur = cur->next;
        curNew->next = cur ? cur->next : NULL;
        curNew = curNew->next;
    }

    return headNew;
}

};

“`有点模糊

0 赞同 0 条回复

普通 2023年7月8日下午11:11

c++ 代码哈希
class Solution {
public:
Node* copyRandomList(Node* head) {
if(head nullptr) return nullptr;
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];
}
};
c++ 重组拆分代码
class Solution {
public:
Node copyRandomList(Node* head)
{
if(headNULL) return NULL;
Node* cur=head;
while(cur)//构建新的链表
{
Node* temp=new Node(cur->val);
temp->next=cur->next;
cur->next=temp;
cur=temp->next;
}
cur=head;
while(cur)//重新指定Random
{
if(cur->random!=NULL)
cur->next->random=cur->random->next;
cur=cur->next->next;
}
Node* pre=head;
Node *fol=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 fol;
}
};

0 赞同 0 条回复

阿尚普通 2023年7月8日下午11:04

//哈希表解法
class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) return null;

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

        Node n = head;

        while(n != null){
            Node copyNode = new Node(n.val);
            nodeMap.put(n, copyNode);
            n = n.next;
        }

        n = head;
        while(n != null){
            Node node = nodeMap.get(n);
            node.next = nodeMap.get(n.next);
            node.random  = nodeMap.get(n.random);

            n = n.next;
        }

        return nodeMap.get(head);
    }
}

0 赞同 0 条回复

#00456B 普通 2023年7月8日下午11:03

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

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head == NULL){
            return head;
        }
        //假设原链表为ABC
        Node* cur = head;
        //copy list
        //新链表为原链表的每个节点的复制，为A1 B1 C1
        //将两个链表合在一起A->A1->B->B1->C->C
        while(cur){
            Node* nodeNew = new Node(cur->val);
            nodeNew->next = cur->next;
            cur->next = nodeNew;
            cur = cur->next->next;//因为穿插了新链表，所以在原链表上遍历需要走两步
        }
        //copy list->random
        cur = head;
        while(cur){
            Node* curNew = cur->next;//这是新链表的每个节点，即A1是A的next
            if(cur->random){
                curNew->random = cur->random->next;
                //不是curNew->random = cur->random;
                //因为cur->random指向的还是原链表中的节点的random，真正需要连接的是这个random的next
            } 
            else{
                curNew->random = NULL;
            }
            cur = cur->next->next;//同上，遍历需要走两步
        }
        //split
        //此时两个链表的关系如下：
        //对于next指针，他们的关系还是A->A1->B->B1->C->C
        //对于random指针，两个链表都是自己内部的连接
        //所以只需要把next指针进行拆分，就可以得到完整的新链表了
        Node* headNew = head->next;//这是记录新链表的head
        cur = head;
        while(cur){
            Node* curNew = cur->next;
            cur->next = cur->next->next;//这里已经开始拆分两个链表了
            if(curNew->next){
                curNew->next = curNew->next->next;
            }
            else{
                curNew->next = NULL;
            }
            cur = cur->next;
        }
        return headNew;
    }
};

0 赞同 0 条回复

北辰普通 2023年7月8日下午10:44

public Node copyRandomList(Node head) {
        if(head==null) {
            return head;
        }
        Node p = head;
        //复制链表结点
        while(p!=null) {
            Node q = p.next;
            p.next = new Node(p.val);
            p.next.next = q;
            p=q;
        }
        //更改random域
        p=head;
        while(p!=null) {
            Node q = p.next;
            q.random = p.random==null?null:p.random.next;
            p = p.next.next;
        }
        //拆解
        p = head;
        Node ans = p.next;
        while(p!=null) {
            Node q = p.next;
            p.next = q.next;
            p = q.next;
            q.next = p==null?null:p.next;
            q = p==null?null:p.next;
        }
        return ans;
    }

时间复杂度：O（n)
空间复杂度：O（n）

0 赞同 0 条回复

醒醒醒醒普通 2023年7月8日下午10:31

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

        //fuzhisuiji
        cur = head;
        while (cur){
            Node* curNew = cur->next;
            curNew->random = cur->random ? cur->random->next :nullptr;
            cur = cur->next->next;
        }

        //chaifen
        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年7月8日下午10:12

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;
        }
        // 构建next和random
        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）

0 赞同 0 条回复

桎梏普通 2023年7月8日下午8:58

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

    }
}

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

0 赞同 0 条回复

CaCO3 永久会员 2023年7月8日下午8:37

”’java
class Solution {
public Node copyRandomList(Node head) {
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);
}
}
”’
时间复杂度O(n)
空间复杂度O(N)

0 赞同 0 条回复

土豆芋泥包_ 普通 2023年7月8日下午8:29

代码如下

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日下午8:27

边界判断、复制节点、复制随机节点、拆分

var copyRandomList = function(head) {
    // 边界判断
    if(!head) return null
    // 复制节点
    let cur = head
    while(cur) {
        let next = cur.next
        cur.next = new Node(cur.val)
        cur.next.next = next
        cur = next
    }

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

    // 拆分
    let newHead = head.next
    cur = head
    curNew = head.next
    while(cur) {
        cur.next = cur.next.next
        cur = cur.next
        curNew.next = cur === null ? null : cur.next
        curNew = curNew.next
    }
    return newHead
};

0 赞同 0 条回复

H、普通 2023年7月8日下午7:15

先拼接，再拆分

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

Luminous 普通 2023年7月8日下午7:05

/*
// 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;
        //复制链表中的next
        Node cur=head;
        while(cur!=null){
            //创建新节点
            Node newCur=new Node(cur.val);
            Node next=cur.next;
            cur.next=newCur;
            newCur.next=next;
            cur=next;
        }
        //复制链表中的random
        cur=head;
        while(cur!=null){
            Node next=cur.next;
            next.random= cur.random==null?null:cur.random.next;
            cur=next.next;
        }
        //拆分链表
        Node newHead=head.next;
        cur=head;
        Node newCur=newHead;
        while(cur!=null){
            cur.next=newCur.next;
            cur=cur.next;
            newCur.next= cur==null?null:cur.next;
            newCur=newCur.next;
        }
        return newHead;
    }
}

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

0 赞同 0 条回复

一琬人间烟火普通 2023年7月8日下午5:18

C++,使用map
class Solution {
public:
Node* copyRandomList(Node* head) {
Node* cur=head;
unordered_map<Node,Node> m;
while(cur!=NULL){
m[cur] = new Node(cur->val);
cur=cur->next;
}
cur=head;
while(cur!=NULL){
m[cur]->next=m[cur->next];
m[cur]->random=m[cur->random];
cur=cur->next;
}
return m[head];
}
};

0 赞同 0 条回复

ONE PIECE 普通 2023年7月8日下午3:50

/*
// 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 pre = head;
        //1、复制节点
        while(pre!=null){
            map.put(pre,new Node(pre.val));
            pre=pre.next;
        }
        pre=head;
        //2、复制next和random
        while(pre!=null){
            map.get(pre).next=map.get(pre.next);
            map.get(pre).random=map.get(pre.random);
            pre=pre.next;
        }
        return map.get(head);
    }
}

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

0 赞同 0 条回复

波雅汉库克普通 2023年7月8日下午2:44

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

        node = head;
        while(node!=nullptr){
            mp[node]->next = mp[node->next];
            mp[node]->random = mp[node->random];
            node = node->next;
        }

        return mp[head];
    }
};

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

0 赞同 0 条回复

长河呼叫黄江普通 2023年7月8日下午2:21

2023.7.8
Day2：下面是代码
一般理解，之后还要再刷再理解。

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

0 赞同 0 条回复

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

共以下 51 个回答

哈希表

# 回答此问题取消回复

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

共以下 51 个回答

哈希表

# 回答此问题 取消回复

# 回答此问题取消回复