题目描述

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.

Example 1:

Input:
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}

Explanation:
Node 1's value is 1, both of its next and random pointer points to Node 2.
Node 2's value is 2, its next pointer points to null and its random pointer points to itself.

Note:

1. You must return the copy of the given head as a reference to the cloned list

题意：复制一个带有随机指针的单向链表。

算法1

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

题解：其实这题还是比较难想的。解题步骤如下：（建议大家手画一个简图加深理解）

• 先在每个节点后面新建一个val值相同的节点。
• 对每个原来的节点执行:$p.next.random = p.random.next$。
• 再将两个相同的链表拆分开来。

C++ 代码

    Node* copyRandomList(Node* head) {
        if(!head) return NULL;
          Node* dummy = new Node(0);
        dummy->next = head;
        //每个节点后面新增一个val值相同的心节点
        while(head)
        {
            Node* temp = new Node();
            temp->val = head->val;
            temp->next = head->next;
            head->next = temp;
          head = temp->next;
        }
        head = dummy->next;
        //  为每个新增的节点的随机指针赋值，这里需要主要随机指针为NULL的情况
        while(head)
        {
            head->next->random = (head->random)?head->random->next:NULL;
            head = head->next->next;
        }
        //  将两个链表拆分开来
        head = dummy->next;
        dummy->next = head->next;
        Node* cur = head->next;
        //  注意最后一个节点的NULL
        while(head)
        {
            head->next = cur->next;
            cur->next = (head->next)?head->next->next:NULL;
            head = head->next;
            cur = (cur)?cur->next:NULL;
        }
        return dummy->next;
    }