I 刷题 I — 复制带随机指针的链表

目录

细节点：

解题方法：

代码实现：

---

138. 复制带随机指针的链表 - 力扣（LeetCode）https://leetcode.cn/problems/copy-list-with-random-pointer/ 

细节点：

  1、每个节点中，额外含有一个指针，随机指向原链表中的任意一个节点（包括NULL）

  2、深拷贝：将原链表的进行一次拷贝，拷贝链表中的结构要与原链表保持一致。

       其中除原始节点顺序不变外，拷贝后的每个节点中的随机指针的指向与原链表节点                        中的一 一对应（包括随机指针random）。

             

 

解题方法：

1. 首先：将每个拷贝节点连接在原链表后，如下图：

 

       这样就可以用一个很妙的式子： copy->random = prev->random->next  ；

           prev记录的是，原链表的节点地址 。

2.然后：遍历拷贝链表，将拷贝节点中 random 按原链表的结构依次拷贝 。

3.因为题干要求返回拷贝链表的头节点地址，所以我们还要将拷贝链表与原链表 “ 解开 ” ，如下：

代码实现：

    Node* copyRandomList(Node* head) {
        Node* pphead = head;
        if(head == NULL)
        return NULL;
        Node* Next = head->next;

        //将copy节点连接到原链表
        for(int i = 0;head!=NULL;head = Next)
        {
            Next = head->next;
            Node* NewNode = (Node*)malloc(sizeof(Node));
            head->next = NewNode;
            NewNode->val = head->val;
            NewNode->next = Next;
        }

        //将copy节点的random按原链表结构拷贝
        Node* NEWhead = pphead->next;
        head = pphead;
        Node* prev = pphead;
        Node* temp = NEWhead;
        for(;prev!=NULL;)
        {
            if(prev->random!=NULL)
            {
                temp->random = prev->random->next;
            }
            else
            {
                temp->random = NULL;
            }
            prev = temp->next;
            if(prev == NULL)
            break;
            temp = temp->next->next;
        }

        //将拷贝链表与原链表解开，并将原链表复原
        prev = pphead;
        for(temp = NEWhead;temp->next!=NULL;temp = temp->next)
        {
            prev->next = temp->next;
            prev = temp->next;
            temp->next = temp->next->next;
        }
        prev->next = NULL;
        return NEWhead;
    }