当前位置 博文首页 > 文章内容

    剑指35 复杂链表的复制

    作者: 栏目:未分类 时间:2020-07-04 16:02:09

    本站于2023年9月4日。收到“大连君*****咨询有限公司”通知
    说我们IIS7站长博客,有一篇博文用了他们的图片。
    要求我们给他们一张图片6000元。要不然法院告我们

    为避免不必要的麻烦,IIS7站长博客,全站内容图片下架、并积极应诉
    博文内容全部不再显示,请需要相关资讯的站长朋友到必应搜索。谢谢!

    另祝:版权碰瓷诈骗团伙,早日弃暗投明。

    相关新闻:借版权之名、行诈骗之实,周某因犯诈骗罪被判处有期徒刑十一年六个月

    叹!百花齐放的时代,渐行渐远!



    请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。

     

    这题首先思路就比较复杂。

    如果直接复制好基础链表,再复制random指针,就需要O(n^2)的时间,比较慢。

    如果用哈希表记录下来每个节点的指针,可以化简到O(n),但是也需要O(n)的辅助空间。

    最优方法为先复制每个节点,并插入在原节点后面;然后为每个复制节点建立random指针,这样random的目标直接就是原节点random的下一个节点;最后把复制的节点拆出来即可。

    这里有两个点需要注意,一个是一定要留一个dummyhead指针指向链表头,否则会出现返回的是链表尾的情况;

    第二个是在复制或者建立random指针时,原指针和copy指针会同步往后移动,要注意先移动原指针,因为最多也是移动为nullptr,同时在移动copy指针前要判断原指针是否已经为null,否则会出现访问null的情况。

     1 /*
     2 // Definition for a Node.
     3 class Node {
     4 public:
     5     int val;
     6     Node* next;
     7     Node* random;
     8     
     9     Node(int _val) {
    10         val = _val;
    11         next = NULL;
    12         random = NULL;
    13     }
    14 };
    15 */
    16 class Solution {
    17 public:
    18     Node* copyRandomList(Node* head) {
    19         if(head==nullptr)
    20             return nullptr;
    21         return copyeach(head);
    22     }
    23 
    24     Node* copyeach(Node* head){
    25         Node* cur=head;
    26         while(cur!=nullptr){
    27             Node* copy=new Node(cur->val);
    28             copy->next=cur->next;
    29             cur->next=copy;
    30             cur=copy->next;
    31         }
    32         return establish_random(head);
    33     }
    34 
    35     Node* establish_random(Node* head){
    36         Node* origin=head,*copied=head->next;
    37         while(origin!=nullptr){
    38             if(origin->random!=nullptr){
    39                 copied->random=origin->random->next;
    40             }
    41             origin=copied->next;
    42             if(origin!=nullptr)
    43                 copied=origin->next;
    44         }
    45         /*
    46         Node* temp=head;
    47         while(temp!=nullptr){
    48             if(temp->random!=nullptr)
    49                 cout<<"val:"<<temp->val<<",random:"<<temp->random->val<<endl;
    50             else
    51                 cout<<"val:"<<temp->val<<",null"<<endl;
    52             temp=temp->next;
    53         }
    54         */
    55         return split(head);
    56     }
    57 
    58     Node* split(Node* head){
    59         Node* copied=head->next,*dummyhead=copied;
    60         while(head!=nullptr){
    61             head->next=copied->next;
    62             head=head->next;
    63             if(head==nullptr)
    64                 break;
    65             copied->next=head->next;
    66             copied=copied->next;
    67         }
    68         return dummyhead;
    69     }
    70 };