题目描述

请实现一个函数可以复制一个复杂链表。

在复杂链表中，每个结点除了有一个指针指向下一个结点外，还有一个额外的指针指向链表中的任意结点或者null。

注意：

函数结束后原链表要与输入时保持一致。

样例

输入：[1, 2, 3]
输出：[1, 2, 3]

算法

(链表) $O(n)$

不使用额外空间，分三步处理

1. 遍历一遍链表，在每个节点的后面插入一个与当前节点值相同的节点
2. 再遍历一遍，对于原链表中有 random 域的节点进行赋值 p->next->random = p->random->next
3. 最后将复制出来的链表拆分出来，同时恢复原链表的结构

时间复杂度

遍历链表的时间复杂度是 $O(n)$

C++ 代码

/**
 * 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) {
        // 1. 复制每个节点接到它的后面
        for (auto p = head; p;)
        {
            auto np = new ListNode(p->val);
            auto next = p->next;
            p->next = np;
            np->next = next;
            p = next;
        }

        // 2. 为复制出来节点的 random 域赋值
        for (auto p = head; p; p = p->next)
            if (p->random)
            {
                p->next->random = p->random->next;
                if (p->next) p = p->next;
            }

        // 3. 将复制出来的链表从原链表中拆出来
        auto dummy = new ListNode(-1);
        auto cur = dummy;
        for (auto p = head; p; p = p->next)
        {
            cur->next = p->next;
            p->next = p->next->next;
            cur = cur->next;
        }

        return dummy->next;
    }
};