JZTXT

复杂链表的复刻

发布时间 2023-04-04 11:29:15作者: 穿过雾的阴霾

暴力做法

时间复杂度 O (n^2)

  1. 遍历一遍，复制 next 指针，新建链表
  2. 遍历第二遍，复制 random 指针，查找每一个 random 节点的位置
class Solution {
public:
    ListNode *copyRandomList(ListNode *head) {
        ListNode* dummy=new ListNode (-1),*tail=dummy;
        if(!head)   return dummy->next;
        //遍历一遍，复制next指针
        for(auto p=head;p;p=p->next)
            tail=tail->next=new ListNode(p->val);
        //遍历第二遍，复制random指针
        tail=dummy->next;
        for(auto p=head;p;p=p->next,tail=tail->next)
            if(p->random)//从头开始寻找random指针指向的地方
            {
                auto t=dummy->next,t2=head;//t和t2分别指向新旧链表
                while(t2!=p->random)//两指针同时往后走，直到找到random
                {
                    t=t->next;
                    t2=t2->next;
                }
                tail->random=t;
            }
        return dummy->next;
    }
};

哈希做法

暴力复杂度主要用于查找 random 节点，我们可以哈希存储原链表和新链表节点的对应关系，实现O (1) 查找

/**
 * Definition for singly-linked list with a random pointer.
 * struct ListNode {
 *     int val;
 *     ListNode *next, *random;
 *     ListNode(int x) : val(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *copyRandomList(ListNode *head) {
        ListNode* dummy=new ListNode (-1),*tail=dummy;
        if(!head)   return dummy->next;
        unordered_map<ListNode*,ListNode*> hashtable;
        //遍历一遍，复制next指针，同时记录新旧链表节点的对应关系
        for(auto p=head;p;p=p->next)
        {
            tail=tail->next=new ListNode(p->val);
            hashtable[p]=tail;
        }
        //遍历第二遍，复制random指针
        tail=dummy->next;
        for(auto p=head;p;p=p->next,tail=tail->next)
            if(p->random)
                tail->random=hashtable[p->random];
                
        return dummy->next;
    }
};