题目描述

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

val: an integer representing Node.val
random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.

算法1

3次遍历，妙用新老节点的next指针 $O(n)$

要遍历老链表 3次
第一遍，创建拷贝节点，令 a 的copy为 a’, 并使得 a’->next = a->next, a->next = a’
第二遍，填充 a’->random
第三遍，使得 a->next 重新指向 老链表的 下一个, a’->next 指向新链表的下一个

C++ 代码

Node* copyRandomList(Node* head) {
    if(!head) return head;

    // 第一遍
    auto p = head;
    while(p) {
        Node* copy = new Node(p->val);
        copy -> next = p->next;
        p->next = copy;
        p = copy->next;
    }
    // 第二遍
    p = head;
    while(p) {
        auto copied = p->next;
        copied->random = p->random ? p->random->next : nullptr;
        p = copied->next;
    }
    // 第三遍
    p = head;
    auto new_head = p->next;
    while(p) {
        auto copied = p->next;
        p->next = copied->next;
        copied->next = p->next ? p->next->next : nullptr;
        p = p->next;
    }

    return new_head;
}