题目描述

搬用工，然后自己可劲儿备注为了自己看懂~
1.遍历链表依次在本来结点后面添加他的复制结点np；
2.如果说这个结点有random,那么就：自己画图好好寻思吧，2333
3.最后把复制结点提炼出来成新链表，这里需要先定义一个虚假的头结点和尾结点。

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析：blablabla

C++ 代码

class Solution {
public:
    ListNode *copyRandomList(ListNode *head) {
        //开始遍历添加p的复制点np;
        for(auto p = head; p;) {
            auto np = new ListNode(p->val);
            auto next = p->next;
            p->next = np;
            np->next = next;
            p = next;
        }
        //如果存在p 有random 则可以通过图理解：p->next-random 为新复制点的random,因为此时p->next不再是以前的next
        for(auto p=head; p;p=p->next->next){//这一咕噜卡死我了，痛哭流涕，哈哈哈
            if(p->random)
                p->next->random = p->random->next;
           // p = p->next->next;

        }

        auto dummy = new ListNode(-1);
        auto cur = dummy;//需要一个尾结点
        for(auto p= head; p;p=p->next) {

        cur->next = p->next;//开始尾结点的next赋值为p的next
        cur = cur->next;//向后移动cur和p
        p = p->next;

        }
        return dummy->next;
    }
};

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析：blablabla

C++ 代码

blablabla