搜索

复制,就需要和原链表的地址不同,不能引用原地址,因此你需要开辟新的空间。
正常情况下,你只需要遍历下面,但现在是复杂链表,random指向任意的节点,所以
如果你只是遍历多次,你可能遇到指向的节点,在遍历时候还没有创建,或者创建成功了,每次去查找它,让时间复杂度何其复杂,所以我们要存储节点
这里,介绍两种方法

法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 == nullptr) return nullptr;
        Node* cur = head;
        unordered_map<Node*, Node*> 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];
    }
};

解析:
按实例,如果节点为空,直接输出null。
c++使用哈希表借助unordered_map,
我们先通过遍历创建哈希表,
例如,map[A] = A*
这里的A是指链表指针的原地址,A*注意了,是你重新开辟的值为A的节点!因为是复制,所以不能引用原地址。
然后再给新节点random和next指针引用新节点。这里的循环依旧通过原地址去映射找出新节点。
我这里,一开始的想法是:

map[cur]->next = cur->next;
map[cur]->random = cur->random;

实际上,又引用了原节点,是错的,大家应该避免。

方法,拼接和拆分

原链表为,A->B->C
那我们就要创建A->A->B->B->C->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 == nullptr) return nullptr;
        Node* cur = head;
        // 复制新节点拼接,这里建议大家画图,能够更加清楚认识。
        while(cur != nullptr) {
            Node* tmp = new Node(cur->val);
            tmp->next = cur->next;
            cur->next = tmp;
            cur = tmp->next;
        }
        cur = head;
        // 给新节点random和next指向,注意,你指向的需要是新节点,是next的next
        while(cur != nullptr){
            if(cur->random != nullptr)
                cur->next->random = cur->random->next;
            cur = cur->next->next;
        }
        // 拆分
        Node* pre = head,*res = head->next;
        cur = head->next;
        while(cur->next!=nullptr){
            pre->next = pre->next->next;
            cur->next = cur->next->next;
            pre = pre->next;
            cur = cur->next;
        }
       // 这里只是为了完整,把原链表分离出来,最后指向null,而为什么新链表不用指了呢?
       // 因为新链表用了原链表最后的null,在前面的创建中,新节点->null
        pre->next = nullptr;
        return res;
    }
};

这里还要讨论两个while循环,为什么一个是判断cur!=nullptr,而另一个却是cur->next

起始点不一样,第一个是head,第二个是head->next
因为复制在原链表的原因,旧节点后面必然接着新节点,所以cur的next必然有,如果cur是null,那自然不需要了。
后面我们在分离,我们就要知道,实际我们判断的是cur/head的next的next,新链表最后必接了null,所以这样不会造成next的next,nul的next还是null的错误了。

版权属于:染念
作品采用:本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
3
查看目录

目录

来自 《LeetCode138|剑指 Offer 35. 复杂链表的复制》
评论

博主很懒,啥都没有