思路

在原链表的两个结点中间新开一个结点，值和两个结点中的前一个相同，如下图：

这样子我们复制$random$的值就只要p->next->random=p->random->next。

代码

/**
 * 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) {
        //添上新结点
        for (auto p = head; p; p = p -> next -> next)
        {
            auto q = new ListNode(p -> val);
            auto next = p -> next;
            p -> next = q;
            q -> next = next;
        }
        //处理random
        for (auto p = head; p; p = p -> next -> next)
        {
            if (p -> random)
                p -> next -> random = p -> random -> next;
        }
        //把添上的结点弄到新链表里
        auto dummy = new ListNode(-1);
        auto q = dummy;
        for (auto p = head; p; p = p -> next)
        {
            q -> next = p -> next;
            //这里要复原链表（y总视频是错的）
            p -> next = p -> next -> next;
            q = q -> next;
        }
        return dummy -> next;
    }
};

感谢观看！(^o^)／

$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\mathcal{writer\enspace by \enspace acwing}$ : $\mathfrak{天元之弈}$