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

mpweixin用户普通 2024年4月1日下午5:40

python”’
def copyRandomList(self, head):
“””
:type head: Node
:rtype: Node
“””
# 返回 RandomListNode
if head is None:
return None
# 复制
temp = head
while temp:
node = Node(temp.val)
node.next = temp.next
temp.next = node
temp = node.next

    # 实现新建node的random指向
    temp = head 
    while temp:
        if temp.random: 
            temp.next.random = temp.random.next 
        temp = temp.next.next
    # 拆分成两个链表
    Nhead = head
    res = head.next
    while head.next:
        tmp = head.next
        head.next = tmp.next
        head = tmp
    return res

复制和拆分的思路，建立兄弟链接为temp.next.random=temp.random.next
时间复杂度为O(n)，空间复杂度为O(n)

0 赞同 0 条回复

雨落星空普通 2024年3月10日上午10:49

”’python
思路：先复制链表，再将链表进行拆分
class Solution(object):
def copyRandomList(self, head):
“””
:type head: Node
:rtype: Node
“””
if not head:
return None
# 复制链表节点
cur = head
while cur:
next = cur.next
cur.next = Node(cur.val)
cur.next.next = next
cur = next

    # 复制随机节点
    cur = head
    while cur:
        curNew = cur.next
        curNew.random = cur.random.next if cur.random else None
        cur = cur.next.next

    # 拆分,比如把 A->A1->B->B1->C->C1拆分成 A->B->C和A1->B1->C1
    headNew = head.next
    cur = head
    curNew = head.next
    while cur:
        cur.next = cur.next.next
        cur = cur.next
        curNew.next = cur.next if cur else None
        curNew = curNew.next

    return headNew

0 赞同 0 条回复

莫～慢～待普通 2024年3月9日下午8:53

class Solution {
public Node copyRandomList(Node head) {
HashMap<Node,Node> hashmap=new HashMap<>();
Node virhead=new Node(-1);
Node temp_new=virhead;
Node temp=head;
while(temp!=null)
{
temp_new.next=new Node(temp.val);
hashmap.put(temp,temp_new.next);
temp=temp.next;
temp_new=temp_new.next;
}
temp_new=virhead;
temp=head;
while(temp!=null)
{
temp_new.next.random=hashmap.get(temp.random);
temp=temp.next;
temp_new=temp_new.next;
}
return virhead.next;
}
}
通过哈希表，记录之前链表和新链表节点之间的映射关系，从而完成新链表random指针的赋值

0 赞同 0 条回复

e=mc² 普通 2024年3月6日下午9:39

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

        // A->B->C 复制为 A->A1->B->B1->C->C1
        // 指针节点
        Node curr = head;
        while (curr != null) {
            // 保留后续节点
            Node temp = curr.next;
            // A->A1
            curr.next = new Node(curr.val);
            // A->A1->后续节点
            curr.next.next = temp;
            // 指针后移
            curr = temp;
        }

        // 复制radom节点 curr节点是指针 重置为head从头复制
        // 重置head的指针节点
        curr = head;
        while (curr != null) {
            // 保留后续节点
            Node temp = curr.next;
            // A1.randon = A.randon.next(randon指向的不带脚标的 .next是复制的带脚标的)
            temp.random = curr.random == null ? null : curr.random.next;
            // 只处理带脚标的
            curr = curr.next.next;
        }


        // A->A1->B->B1->C->C1拆分成A->B->C
        // 从A1开始的被操作节点
        Node result = head.next;
        curr = head;
        // 从A1开始的指针节点
        Node resultCur = head.next;
        while (curr != null) {
            // A->A1 变为 A->B
            curr.next = curr.next.next;
            // 下一步从B开始
            curr = curr.next;
            // A1->B 变为 A1->B1
            resultCur.next = curr == null ? null : curr.next;
            // 下一步从B1开始
            resultCur = resultCur.next;
        }
        return result;
    }
}

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

0 赞同 0 条回复

Yeah~ 普通 2024年3月6日下午3:35

“c++
class Solution {
public:
Node* copyRandomList(Node* head) {
if(head nullptr){
return nullptr;
}
Node* tmp = head;
while(tmp){
Node* new_h = new Node(tmp->val);
new_h->next = tmp->next;
tmp->next = new_h;
tmp = tmp->next->next;
}
tmp = head;
while(tmp){
if(tmp->random nullptr){
tmp->next->random = nullptr;
}else{
tmp->next->random = tmp->random->next;
}
tmp = tmp->next->next;
}
tmp = head;
Node* newhead = new Node(0);
Node* cur = newhead;
while(tmp){
cur->next = tmp->next;
cur = cur->next;
tmp->next = tmp->next->next;
tmp = tmp->next;
}
return newhead->next;
}
};
时间空间都为O(n)

0 赞同 0 条回复

30tcq 普通 2024年3月6日下午3:17

思路：第一次很难想到先复制再拆分的想法

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

    //分离链表
    cur = head;
    Node *newHead = cur->next;
    Node *curNew= cur->next;
    while(cur != NULL){
        Node *tp1 = cur->next->next;
        cur->next = cur->next->next;
        cur = cur->next;

        curNew->next = cur ? cur->next : NULL;
        curNew = curNew->next;
    }
    return newHead;
}

};

“`
犯错：思路混乱，且没有考虑到cur->random为空的情况
时间复杂度O(N)
空间复杂度O(N)

0 赞同 0 条回复

YOLO 普通 2024年3月6日上午11:16

/*请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了
有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null*/
class Solution {
    public Node copyRandomList(Node head) {
        if(head == null)
            return null;

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

        //复制随机节点
        temp = head;
        while(temp != null){
            Node tempNew = temp.next;
            if(temp.random == null)
                tempNew.random = null;
            else{
                tempNew.random = temp.random.next;
            }
            //tempNew.random = temp.random == null ? null : temp.random.next;
            temp = temp.next.next;
        }

        //复制+拆分链表
        Node headNew = head.next;
        temp = head;
        Node tempNew = head.next;
        while(tempNew.next != null){
            temp.next = temp.next.next;
            tempNew.next = tempNew.next.next;
            temp = temp.next;
            tempNew = tempNew.next;
        }
        temp.next =null;  //单独处理原链表尾节点
        return headNew;   //返回新链表头节点

    }
}

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月5日上午8:22

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

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

        // 复制链表节点
        Node* cur = head;
        while(cur) {
            Node* newNode = new Node(cur->val);
            newNode->next = cur->next;
            cur->next = newNode;
            cur = cur->next->next;
        }

        //赋值随机指针
        cur = head;
        while(cur) {
            cur->next->random = (cur->random != nullptr) ? cur->random->next : nullptr;
            cur = cur->next->next;
        }

        // 拆分
        Node* newHead = head->next;
        cur = head;
        while(cur) {
            Node* newNode = cur->next;
            cur->next = cur->next->next;
            newNode->next = (newNode->next != nullptr) ? newNode->next->next : nullptr;
            cur = cur->next;
        }
        return newHead;
    }
};

0 赞同 0 条回复

繁星普通 2024年3月5日上午12:06

哈希，时间复杂度O(n),空间复杂度O(n)
class Solution {
public Node copyRandomList(Node head) {
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) {
Node temp = map.get(cur);
temp.next = map.get(cur.next);
temp.random = map.get(cur.random);
cur = cur.next;
}
return map.get(head);
}
}

0 赞同 0 条回复

Deckkker 普通 2024年3月5日上午12:03

class Node:  
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):  
        self.val = int(x)  
        self.next = next  
        self.random = random  

def copyRandomList(head: 'Node') -> 'Node':  
    if not head:  
        return None  

    # 第一步：复制节点并插入到原节点之后  
    cur = head  
    while cur:  
        copy_node = Node(cur.val)  
        copy_node.next = cur.next  
        cur.next = copy_node  
        cur = copy_node.next  

    # 第二步：更新复制节点的random指针  
    cur = head  
    while cur:  
        if cur.random:  
            cur.next.random = cur.random.next  
        cur = cur.next.next  

    # 第三步：拆分链表，构建新的复制链表头部  
    dummy = Node(0)  # 创建一个哑节点作为新链表的头部  
    new_head = dummy  
    cur = head  
    while cur:  
        copy_node = cur.next  
        cur.next = copy_node.next  
        new_head.next = copy_node  
        new_head = new_head.next  
        cur = cur.next  

    return dummy.next

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

0 赞同 0 条回复

　南木普通 2024年3月4日下午6:14

这里复制指深拷贝，第一次看到这道题给搞晕了

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

一颗红豆普通 2024年3月4日下午5:50

时间复杂度o（n），空间复制度o（1）
分为复制节点、复制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(headnullptr)
{
return nullptr;
}
//复制各节点
Node *cur = head;
Node *temp = head->next;
while(cur!=nullptr)
{
cur->next = new Node(cur->val);
cur->next->next = temp;
cur = temp;
temp = curnullptr?nullptr:cur->next;
}
//复制random节点
cur = head;
Node *randomptr = head->next;
while(cur!=nullptr)
{
randomptr->random = cur->randomnullptr?nullptr:cur->random->next;
cur = cur->next->next;
randomptr = randomptr->nextnullptr?nullptr:randomptr->next->next;
}
//拆分链表
cur = head;
Node *result = head->next;
Node *p1 = result;
while(cur!=nullptr)
{
cur->next = cur->next->next;
p1->next = p1->nextnullptr?nullptr:p1->next->next;
cur = cur->next;
p1 = p1->next;
}
return result;
}
};

0 赞同 0 条回复

mpweixin用户普通 2024年3月4日下午5:43

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);
}
k神的题解还要再想一下

0 赞同 0 条回复

Jankin 普通 2024年3月4日下午5:37

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

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

0 赞同 0 条回复

kfaebot 普通 2024年3月4日下午4:59

/*
// 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 *tmp=head;
        //创建哈希表
        unordered_map<Node*,Node*> hash;
        //遍历原始链表复制节点
        while(tmp!=nullptr){
            hash.insert(pair<Node*,Node*>(tmp,new Node(tmp->val)));
            tmp=tmp->next;
        }

        //重新遍历链表复制节点的指向
        tmp=head;
        while(tmp!=nullptr){
            hash[tmp]->next=hash[tmp->next];
            hash[tmp]->random=hash[tmp->random];
            tmp=tmp->next;
        }
        return hash[head];
    }
};

0 赞同 0 条回复

南梁陈庆之普通 2024年3月4日下午4:42

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

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

        return map.get(head);
    }
}

哈希表解法，设置每个节点都是一项值，key值为当前节点对象，val值为节点的数值
遍布链表，设置每个节点的next节点为哈希表中获取其对象；

0 赞同 0 条回复

Raphtalia. 普通 2024年3月4日下午3:26

/*
// 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* tmp = head;
while(tmp){
Node* ntmp = new Node(tmp->val);
ntmp->next = tmp->next;
tmp->next = ntmp;
tmp = ntmp->next;
}
//random更新
tmp = head;
while(tmp){
if(tmp->random != nullptr)
tmp->next->random = tmp->random->next;
tmp = tmp->next->next;
}
//拆分
Node* cur = head->next;
Node* pre = head, *res = head->next;
while(cur->next){
pre->next=pre->next->next;
cur->next=cur->next->next;
pre = pre->next;
cur = cur->next;
}
pre->next = nullptr;
return res;
}
};

0 赞同 0 条回复

HU 普通 2024年3月4日上午5:25

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

    // 先复制节点
    let cur = head;
    while(cur != null) {
        const 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;
    }

    // 拆分：把A->A1->B->B1->C->C1->NULL拆分成A->B->C->NULL和A1->B1->C1->NULL
    cur = head;
    const res = cur.next;
    curNew = res;
    while(cur != null) {
        cur.next = curNew.next;
        cur = cur.next;
        curNew.next = cur == null ? null : cur.next;
        curNew = curNew.next;
    }

    return res;
};

0 赞同 0 条回复

零普通 2024年3月4日上午12:15

思路：Map存储新旧列表的节点，复杂度：O(n)
代码：

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

    return map.get(head);
}

0 赞同 0 条回复

晚风、普通 2024年3月3日下午11:40

class Solution:
def copyRandomList(self, head: ‘Node’) -> ‘Node’:
if not head:
return
hamp = {}

    cur = head
    while cur:
        hamp[cur] = Node(cur.val)
        cur = cur.next

    cur = head
    while cur:
        hamp[cur].next = hamp.get(cur.next)
        hamp[cur].random = hamp.get(cur.random)
        cur = cur.next

    return hamp[head]

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

0 赞同 0 条回复

神经蛙普通 2024年3月3日下午10:34

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

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

};
/
class Solution {
public:
Node copyRandomList(Node* head) {
if(head nullptr) return nullptr;
Node cur = head;
unordered_map<Node, Node*> map;
while(cur)
{
map[cur] = new Node(cur->val);
cur = cur->next;
}
cur = head;
while(cur)
{
map[cur]->next = map[cur->next];
map[cur]->random = map[cur->random];
cur = cur->next;
}
return map[head];
}
};
思路：使用map存下原本的节点和复制节点；从map中取出直接节点赋值next和random指针；
时间复杂度：O（N）空间复杂度O（N）

0 赞同 0 条回复

东普通 2024年3月3日下午10:06

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

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

}
*/

class Solution {
public Node copyRandomList(Node head) {
if (head null) {
return null;
}
Node cur = head;
Node next = null;
// copy node and link to every node
while (cur != null) {
next = cur.next;
cur.next = new Node(cur.val);
cur.next.next = next;
cur = next;
}
cur = head;
Node curCopy = null;
// set copy node random
while (cur != null) {
next = cur.next.next;
curCopy = cur.next;
curCopy.random = cur.random != null ? cur.random.next : null;
cur = next;
}
Node res = head.next;
cur = head;
// split
while (cur != null) {
next = cur.next.next;
curCopy = cur.next;
cur.next = next;
curCopy.next = next != null ? next.next : null;
cur = next;
}
return res;
}
}
时间复杂度为 O(n)
空间复杂度为 O(1)

0 赞同 0 条回复

叫不醒装睡的人普通 2024年3月3日下午9:53

class Solution {
    // 遍历一遍原有链表正常复制原来各节点的数值
    // 遍历同时存在新旧节点的链表，填充新节点中的 random 信息
    // 将链表中的新旧节点分离处理
    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 指针
        // 旧有的节点存在 random 信息，新复制的节点不存在 random 信息
        cur = head;
        while (cur != null) {
            if (cur.random != null) {
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }

        // 克隆完新节点的链表结构：旧->新->旧->新->...
        // 将新链表与原链表分离
        Node newHead = head.next;
        cur = head;
        while (cur != null) {
            // 临时变量记录新复制的节点信息
            Node newNode = cur.next;
            // 从当前旧节点跳到下一个旧节点
            cur.next = newNode.next;
            if (newNode.next != null) {
                // 从当前新节点跳到下一个新节点
                newNode.next = newNode.next.next;
            }
            // 从当前旧节点挪到下一个旧节点
            cur = cur.next;
        }

        // 返回新链表的头节点
        return newHead;
    }
    // 时间复杂度为 O(n)
    // 最差情况是遍历同时包含新旧节点时的链表
    // 空间复杂度为 O(1)
    // 所有的局部变量都是用了常数大小的额外空间
}

0 赞同 0 条回复

Free 普通 2024年3月3日下午8:33

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

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution 
{
public:
    Node* copyRandomList(Node* head) 
    {
        if(head == nullptr)
            return head;
        Node* cur = head;
        while(cur)
        {
            Node* next = cur->next;
            Node* newnode = new Node(cur->val);
            newnode->next = cur->next;
            cur->next = newnode;
            cur = next;
        }
        cur = head;
        while(cur)
        {
            Node* next = cur->next;
            if(cur->random)
                next->random = cur->random->next;
            cur = next->next;
        }

        cur = head;
        Node* res = cur->next;
        while(cur)
        {
            Node* next = cur->next;
            cur->next = cur->next->next;
            if(next && next->next)
                next->next = next->next->next;
            cur = cur->next;            
        }
        return res;
    }
};

时空复杂度O(N)

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年3月3日下午7:02

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

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

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

        // 拆分
       // p=head.next;
        Node headNew = head.next;
        cur = head;
        Node curnew = head.next; //要重新定义，因为上次是在代码块里定义的
        while(cur!=null){
            cur.next=curnew.next;
            cur=cur.next;
            curnew.next= cur==null ? null : cur.next;
            curnew=curnew.next;
        }

        return headNew;

    }
}

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

0 赞同 0 条回复

Yuki 永久会员 2024年3月3日下午6:24

复制复杂链表
https://leetcode.cn/problems/fu-za-lian-biao-de-fu-zhi-lcof/solutions/2665412/fu-zhi-fu-za-lian-biao-by-yukislab-lyrg

0 赞同 0 条回复

lucky耶耶耶*👻*～普通 2024年3月3日下午5:44

public class Solution {
    public Node  Clone(Node  head) {
        //判空
        if (head == null ) {
            return null;
        }
        //复制链表
        Node cur = head;
        while (null != head) {
            Node next = cur.next;
            cur.next = new Node[cur.val];
            cur.next.next = next;
            cur = cur.next;
        }
        //复制随机
        cur = head;
        while (null != head) {
            Node  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 a-b-b-b1-c-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 条回复

Laboratory 普通 2024年3月3日下午5:29

/*
// 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
        Map<Node,Node> map = new HashMap<>();
        Node cur = head;
        while(cur != null) {
            Node node = new Node(cur.val);
            map.put(cur, node);
            cur = cur.next;
        }
        // 构建新节点的next和random
        cur = head; // cur重新指向map
        while(cur != null) {
            Node copyNode = map.get(cur);
            copyNode.next = map.get(cur.next);
            copyNode.random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }
}

0 赞同 0 条回复

Let it be 永久会员 2024年3月3日下午4:40

哈希表方法：
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);
}
}
常规方法：
class Solution {
public Node copyRandomList(Node head) {
if(head null)return null;
Node cur = head;
while(cur != null){
Node tmp = new Node(cur.val);
tmp.next = cur.next;
cur.next = tmp;
cur = tmp.next;
}
cur = head;
while(cur != null){
if(cur.random != null){
cur.next.random = cur.random.next;
}
cur = cur.next.next;
}
cur = head.next;
Node pre = head;
Node res = head.next;
while (cur.next != null){
pre.next = pre.next.next;
cur.next = cur.next.next;
pre = pre.next;
cur = cur.next;
}
pre.next = null;
return res;
}

0 赞同 0 条回复

一期一会普通 2024年3月3日下午4:30

使用哈希表存放节点对
时间复杂度为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 == nullptr) return nullptr;
        Node* p = head;
        unordered_mapmap;
        while(p != nullptr)
        {
            map[p] = new Node(p->val);
            p = p->next;
        }
        p = head;
        while(p != nullptr)
        {
            map[p]->next = map[p->next];
            map[p]->random = map[p->random];
            p = p->next;
        }
        return map[head];
    }
};

0 赞同 0 条回复

方铎码农普通 2024年3月3日下午2:25

使用HashMap作为前后两个链表的关联结构，时间复杂度$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) {
        //map的key是原链表节点，value是新建链表节点
        Map<Node,Node> ans = new HashMap<>();
        Node tmp = head;
        // 将链表的相关数据存储到哈希表中
        while (tmp != null) {
            ans.put(tmp,new Node(tmp.val));
            tmp = tmp.next;
        }
        tmp =head;
        //构建链表的next和random指针
        while(tmp != null){
            ans.get(tmp).next = ans.get(tmp.next);
            ans.get(tmp).random = ans.get(tmp.random);
            tmp = tmp.next;
        }
        return ans.get(head);

    }
}

0 赞同 0 条回复

墨丘俐普通 2024年3月3日下午1:43

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

持之以恒:-) 普通 2024年3月3日下午12:24

使用HashMap映射的方式实现复杂链表复制

根据题解

存在的问题：

简单的链表只需要考虑其next指针，从前向后依次复制即可，复杂链表含有random指针，由于random指针没有固定的对应法则，因此使用双指针进行复制的时候需要依次从前向后遍历，时间复杂度陡增成为O(N2)

使用HashMap解决

   为了解决节点中random指针随机指向的问题，引入HashMap

通过新Node节点和旧Node节点的绑定，依据旧节点next指针和random指针的对应关系，根据HashMap指针O(1)的搜索方式快速的形成对新节点的匹配！

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

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    /***
        链表复制

            使用HashMap存储键值的对应关系，
            因为HashMap的查找速率为O(1)
     */
    public Node copyRandomList(Node head) {
        if(head == null)
            return null;
        Map<Node, Node> map = new HashMap();
        Node searchNode = head;
        // 将新旧两个节点绑定在一块，因为旧节点的值已经是确定的了，那么如果能够根据旧值的对应关系快速的匹配新值的对应关系那将是绝杀！
        while(searchNode != null){
            map.put(searchNode, new Node(searchNode.val));
            searchNode = searchNode.next;
        }
        // 重新赋值
        searchNode = head;
        while(searchNode != null){
            map.get(searchNode).next = map.get(searchNode.next);
            map.get(searchNode).random = map.get(searchNode.random);

        }

        return map.get(head);

    }
}

0 赞同 0 条回复

Jimmy 普通 2024年3月3日上午10:59

思路：先复制链表节点，在复制随机节点，最后对复制的链表进行拆分。图解：https://leetcode.cn/problems/fu-za-lian-biao-de-fu-zhi-lcof/solutions/476617/jian-zhi-offer-35-fu-za-lian-biao-de-fu-zhi-ha-xi-/
时间复杂度 O(N)O(N)O(N) ：三轮遍历链表，使用 O(N)O(N)O(N) 时间。
空间复杂度 O(1)O(1)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) {
        if(head == NULL){
            return NULL;
        }
        //复制链表节点
        Node *cur = head;
        while(cur != NULL){
            Node *temp = cur->next;
            cur->next = new Node(cur->val);
            cur->next->next = temp;
            cur = temp;
        }
        //复制随机节点
        cur = head;
        while(cur != NULL){
            Node *curNew = cur->next;
            curNew->random = cur->random == NULL ? NULL : cur->random->next;
            cur = cur->next->next;
        }

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

😴 普通 2024年3月3日上午10:29

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

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

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

云无深雁影普通 2024年3月3日上午10:00

class Solution {
public Node copyRandomList(Node head) {
HashMap<Node,Node> map = new HashMap();
Node ptr = head;
Node copyHead = new Node(0);
Node copyPtr = copyHead;
while(ptr != null){
copyPtr.next = new Node(ptr.val);
map.put(ptr,copyPtr.next);
copyPtr = copyPtr.next;
ptr = ptr.next;
}
ptr = head;
copyPtr = copyHead.next;
while(ptr != null){
copyPtr.random = map.get(ptr.random);
ptr = ptr.next;
copyPtr = copyPtr.next;
}

    return copyHead.next;
}

}
两次遍历链表。第一次完成next复制并通过hashmap记录对应关系，第二次完成random赋值
时间复杂度On 空间复杂度On

0 赞同 0 条回复

mpweixin用户普通 2024年3月3日上午9:35

class Solution {
public Node copyRandomList(Node head) {
if (head null) return null;
HashMap<Node, Node> hashmap = new HashMap<>();
Node tmp = head;
while (tmp != null) {
hashmap.put(tmp, new Node(tmp.val));
tmp = tmp.next;
}
tmp = head;
while (tmp != null) {
hashmap.get(tmp).next = hashmap.get(tmp.next);
hashmap.get(tmp).random = hashmap.get(tmp.random);
tmp = tmp.next;
}
return hashmap.get(head);
}
}
使用哈希表

0 赞同 0 条回复

Yox 普通 2024年3月3日上午6:15

class Solution:
def copyRandomList(self, head: ‘Node’) -> ‘Node’:
if not head: return
cur = head
# 1. 复制各节点，并构建拼接链表
while cur:
tmp = Node(cur.val)
tmp.next = cur.next
cur.next = tmp
cur = tmp.next
# 2. 构建各新节点的 random 指向
cur = head
while cur:
if cur.random:
cur.next.random = cur.random.next
cur = cur.next.next
# 3. 拆分两链表
cur = res = head.next
pre = head
while cur.next:
pre.next = pre.next.next
cur.next = cur.next.next
pre = pre.next
cur = cur.next
pre.next = None # 单独处理原链表尾节点
return res # 返回新链表头节点
看得题解面试遇到我应该直接说不会

0 赞同 0 条回复

机电皮怪永久会员 2024年3月2日下午11:41

看了题解才做出来
时间复杂度o（2n）
空间复杂度o（n）
##CPP

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if( head == nullptr )
        {
            return nullptr;
        }
        Node* cur = head;
        unordered_map<Node*, Node*> map;

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

        while(cur)
        {
            map[cur]->next = map[cur->next];
            map[cur]->random = map[cur->random];
            cur = cur->next;
        }

        return map[head];
    }
};

0 赞同 0 条回复

Fancy 普通 2024年3月2日下午11:23

哈希表

class Solution:
def copyRandomList(self, head: ‘Node’) -> ‘Node’:
if not head:
return None
# 使用哈希表存储每个节点对应的新节点
dic = {}; cur = head
# 添加映射对
while cur:
dic[cur] = Node(cur.val)
cur = cur.next
# 添加 next 和 random 关系
cur = head
newHead = dic[cur]
while cur:
newHead.next = dic.get(cur.next) #两种获取字典value的方法，get的这种可以容许None
newHead.random = dic[cur.random] if cur.random else None
cur = cur.next
newHead = newHead.next
return dic[head]

拼接

class Solution:
def copyRandomList(self, head: ‘Node’) -> ‘Node’:
# 直接构建成节点1->新节点1->节点2->新节点2 …
# 这样，每个新节点都可以通过旧节点的next访问到了
if not head:
return None
cur = head
while cur:
temp = cur.next
cur.next = Node(cur.val)
cur.next.next = temp
cur = temp
cur = head
while cur:
newCur = cur.next
temp = newCur.next
newCur.next = temp.next if temp else None
newCur.random = cur.random.next if cur.random else None
cur = temp
return head.next

0 赞同 0 条回复

NULL 普通 2024年3月2日下午11:07

class Solution {
public Node copyRandomList(Node head) {
// 如果原链表为空，则直接返回空
if(head null) return null;
Node cur = head;
// 1. 复制各节点，并构建拼接链表
// 遍历原链表，对于每一个节点，创建一个新的节点，其值为原节点的值，然后将新节点插入到原节点和原节点的下一个节点之间
// 即形成一个新的交替排列的链表，原节点的 next 指向新节点，新节点的 next 指向原节点的下一个节点
while(cur != null) {
Node tmp = new Node(cur.val);
tmp.next = cur.next;
cur.next = tmp;
cur = tmp.next;
}

    // 2. 构建各新节点的 random 指向
    // 再次遍历链表，对于每一个原节点，如果其 random 指针不为空，则将其对应的新节点的 random 指针指向原节点 random 指针指向的节点的下一个节点
    // 即新链表中的对应节点
    cur = head;
    while(cur != null) {
        if(cur.random != null)
            cur.next.random = cur.random.next;
        cur = cur.next.next;
    }

    // 3. 拆分两链表
    // 将原链表和新链表分离，即将新链表中的节点提取出来，形成一个新的链表，同时将原链表中的节点的 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 条回复

MARS 普通 2024年3月2日下午10:09

day2第三题

var copyRandomList = function (head) {
  if (head <span class="text-highlighted-inline" style="background-color: #fffd38;"> null) return null
  let map = new Map()</span>

let cur = head
  while (cur) {
    map.set(cur, new Node(cur.val))
    cur = cur.next
  }

cur = head
  while (cur) {
    map.get(cur).next = map.get(cur.next) <span class="text-highlighted-inline" style="background-color: #fffd38;">= undefined ? null : map.get(cur.next);
    map.get(cur).random = map.get(cur.random)
    cur = cur.next
  }</span>

return map.get(head)
};

0 赞同 0 条回复

言之命至普通 2024年3月2日下午10: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;//判断是否为null
            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 条回复

heathhou 普通 2024年3月2日下午9:06

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

        Node * cur = head;
        // 复制节点的值与next指针
        while(cur != nullptr){
            Node * newNode = new Node(cur->val);
            newNode->next = cur->next;
            cur->next = newNode;
            cur = newNode->next;
        }

        // 复制random指针
        cur = head;
        while(cur){
            Node * newNode = cur->next;
            newNode->random = (cur->random == nullptr ?  nullptr : cur->random->next);
            cur = cur->next->next;
        }

        // 拆分,比如把 A->A1->B->B1->C->C1拆分成 A->B->C和A1->B1->C1
        cur = head;
        Node * newHead = cur->next;
        Node * newCur = cur->next;
        while(cur){
            cur->next = cur->next->next;
            cur = cur->next;
            newCur->next = cur ? cur->next : nullptr;
            newCur = newCur->next;
        }

        return newHead;
    }
};

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

0 赞同 0 条回复

进取普通 2024年3月2日下午8:57

class Solution {
public:
Node* copyRandomList(Node* head) {
unordered_map<Node*, Node> map;
Node cur = head;
while (cur != nullptr){
map[cur] = new Node(cur->val);
cur = cur->next;
}
cur = head;
while (cur != nullptr){
map[cur]->next = map[cur->next];
map[cur]->random = map[cur->random];
cur = cur->next;
}
return map[head];
}
};开始完全没思路，甚至都看不懂题。后面看了解析，一知半解，理解了用map来做。时空复杂度都是O(N)

0 赞同 0 条回复

王位詮釋普通 2024年3月2日下午8:21

···java
class Solution {
public Node copyRandomList(Node head) {
Map<Node,Node> hashMap = new HashMap<>();
Node cur = head;
Node cur2 = head;
while(cur!=null){
hashMap.put(cur,new Node(cur.val,null,null));
cur = cur.next;
}
while(cur2!=null){
Node temp = hashMap.get(cur2);
temp.next = hashMap.get(cur2.next);
temp.random = hashMap.get(cur2.random);
cur2 = cur2.next;
}
return hashMap.get(head);
}
}
思路：建立链表中原来的节点与后面重新创建的节点之间的映射，然后通过映射来为新节点设置next和random

0 赞同 0 条回复

是hua不是pua 普通 2024年3月2日下午7:50

“`java
class Solution {
public Node copyRandomList(Node head) {
Node result = new Node(0);
Node tail = result;
Node cur = head;
Map map = new HashMap<>();
while(cur != null){
Node node = new Node(cur.val);
tail.next = node;
tail = node;
Node node2 = new Node(cur.val);
node2 = cur;
map.put(node2, node);
cur = cur.next;
}
cur = head;
tail = result.next;
while(cur != null){
Node random = map.get(cur.random);
tail.random = random;
cur = cur.next;
tail = tail.next;
}
return result.next;
}
}
“` 通过map存储新旧节点的对应关系，从而更新random指针

0 赞同 0 条回复

紫芝普通 2024年3月2日下午6:24

emm参考了别人的思路，初看时没有实现，后续将进一步看一下其他思路，整体理解一下。
时间复杂度: O(n)
空间复杂度：O(n)

“`c++
class Solution {
public:
Node* copyRandomList(Node* head) {
if(head == nullptr) return nullptr;
Node* cur = head;
unordered_map map;
while(cur != nullptr) {
map[cur] = new Node(cur->val);
cur = cur->next;
}
cur = head;
while(cur != nullptr) {
map[cur]->next = map[cur->next];
map[cur]->random = map[cur->random];
cur = cur->next;
}
return map[head];
}
};
“`

0 赞同 0 条回复

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

共以下 48 个回答

使用HashMap映射的方式实现复杂链表复制

存在的问题：

使用HashMap解决

哈希表

拼接

# 回答此问题取消回复

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

共以下 48 个回答

使用HashMap映射的方式实现复杂链表复制

存在的问题：

使用HashMap解决

哈希表

拼接

# 回答此问题 取消回复

# 回答此问题取消回复