48. 复杂链表的复刻

视频

 

题目描述

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

代码：https://www.acwing.com/problem/content/discussion/content/211/

class Solution {
public:
    ListNode *copyRandomList(ListNode *head) {
        //开始遍历添加p的复制点np;
        for(auto p = head; p;) {    //将for(auto p = head; p; )改成for(auto p = head; p; p=p->next)报错
        //后来想明白了，for循环的代码段里面已经对p->next进行了修改,p->next已经不是原链表的第二个元素。大神把
        //本该在for循环语句里面执行的p=p->next发到了for代码段执行，即执行p = next;
            auto np = new ListNode(p->val);//复制p节点,复制的节点为np
            auto next = p->next;//保存原链表中p的下一个节点next
            p->next = np;//把np接在p后面
            np->next = next;//把next接到新点np后面
            p = next;//相当于for语句里面的p=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->next = p->next->next;

        }
        return dummy->next;
    }
};

 这个for循环看来老半天才明白，自己看注释吧。

其他方法： https://www.acwing.com/solution/acwing/content/7963/