LeetCode_LinkedList_138. Copy List with Random Pointer 复制带随机指针的链表（C++）【原地复制节点】

目录

​​一，题目描述​​

​​英文描述​​

​​中文描述​​

​​二，解题思路​​

​​三，AC代码​​

​​C++​​

​​四，解题过程​​

​​第一博​​

一，题目描述

英文描述

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

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.

Return the head of the copied linked 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) that the random pointer points to, or null if it does not point to any node.
Your code will only be given the head of the original linked list.

中文描述

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为  null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。

示例 1：

示例 2：

示例 3：

示例 4：

提示：

0 <= n <= 1000
-10000 <= Node.val <= 10000
Node.random 为空（null）或指向链表中的节点。

来源：力扣（LeetCode）
链接：​​​https://leetcode-cn.com/problems/copy-list-with-random-pointer​​ 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二，解题思路

这一题的主要难点在于，不晓得随机节点的位置。链表不同于数组，定位是个比较麻烦的事。因此当新节点与原节点位置存在某种关系时，便可解决这个问题。

主要有三步：复制节点，复制随机指针，新节点链接为新链表。

假设原链表如下（这里简化起见，省略了随即指针域）：

1，在每个原节点后面链接一个复制节点

2，由于复制节点就在原节点之后，所以随机指针域就比较好确定了（p初始指向head）： 

p->next->random = (p->random == NULL ? NULL : p->random->next);

3，将原链表和新链表各自链接起来

Node * tem = p->next->next;
p->next->next = p->next->next->next;// 将新节点链接起来
p->next = tem;// 保证原链表还是原来的样子
p = tem;

把原链表最后一个节点指向NULL！！！

三，AC代码

C++

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == NULL) return NULL;
        Node * p = head;
        // 在每个原节点后创建一个新节点
        while (p != NULL) {
            Node * node = new Node(p->val);
            node->next = p->next;
            p->next = node;
            p = p->next->next;
        }

        // 重新遍历设置随机指针的值
        p = head;
        while (p != NULL) {
            p->next->random = (p->random == NULL ? NULL : p->random->next);
            p = p->next->next;
        }

        // 将新节点链接起来
        p = head;
        Node * h = head->next;
        while (p != NULL && p->next != NULL && p->next->next != NULL) {
            Node * tem = p->next->next;
            p->next->next = p->next->next->next;// 将新节点链接起来
            p->next = tem;// 保证原链表还是原来的样子
            p = tem;
        }
        p->next = NULL;// 保证原链表最后一个节点的next指向NULL

        return h;
    }
};

四，解题过程

第一博

细节部分还是调了好久的。。。