[数据结构与算法]leetcode 138.复制带随机指针的链表

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

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

复制链表中的指针都不应指向原链表中的节点 。

思路：

1.复制原链表的所有结点，将新结点各自插入到原结点的后面

首先，每次到cur位置，先创建新结点copy，copy->next = cur->next，cur->next = copy

然后，原链表继续向后走，cur = copy->next，然后重复上面操作，直到所有结点复制完毕

2.根据原结点的random，找到复制结点的random

原链表中的第一个结点，7->random = NULL，那么复制结点7->random也是NULL

原链表中的第二个结点，13->random = 7，那么复制结点13->random是复制节点7，也就是原链表的结点13->random->next

copyNode = cur->next，copyNode->random = cur->random->next，
原链表继续向后走，cur = copyNode->next;

原链表中的第三个结点，11->random = 1，那么复制节点11->random是复制结点1，也就是原链表的结点11->random->next

同理，可以得到剩下几个复制节点的random，如下图所示

结束条件是cur==NULL

3.把复制结点解下来，并恢复原链表

初始条件，定义两个指针，分别表示复制链表的头结点和尾结点

再定义两个结点指针，copy = cur->next, next = copy->next，下面拆开链表

复制链表的第一个结点，copyHead记住头结点位置，不再改变，copyHead= copyTail= copy，cur->next = next

cur继续向后走，cur= cur->next

copyTail->next = copy， copyTail = copy，

如此重复下去

直到cur == NULL，循环结束

拆分完成

struct Node* copyRandomList(struct Node* head)
{
    //1.复制链表，并插入到原链表中
    struct Node* cur = head;

    while (cur != NULL)
    {
        //创建新结点
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));

        if (copy == NULL)
        {
            exit(-1);
        }

        copy->val = cur->val;

        //新结点插入到原结点和下一个结点之间
        copy->next = cur->next;

        cur->next = copy;

        cur = copy->next;
    }

    //2.根据原链表中原结点的random，找到复制结点的random

    cur = head;

    while (cur != NULL )
    {
    	//复制链表向后走
        struct Node* copyNode = cur->next;

        if (cur->random == NULL)
        {
            copyNode->random = NULL;
        }
        else
        {
            copyNode->random = cur->random->next;
        }
        //原链表继续向后走
        cur = copyNode->next;
    }
    
    //3.取下新链表，恢复原链表
    cur = head;
 
 	//定义复制链表的头结点、尾结点
    struct Node* copyHead = NULL;
    struct Node* copyTail = NULL;

	while (cur != NULL)
    {
    	//定义两个指针变量，更清晰
        struct Node* copy = cur->next;
        struct Node* next = copy->next;

        if (copyTail == NULL)
        {
            //复制链表头结点
            copyTail = copyHead = copy;
        }
        else
        {
            //复制链表向后走
            copyTail->next = copy;
            copyTail = copy;
        }
		
		//恢复原链表
        cur->next = next;
        
		//原链表继续向后走
        cur = next;
    }
    
  //while (cur != NULL )
    //{
    //    if (cur == head)
    //    {
    //        //新链表头结点
    //        copyHead = copyTail = cur->next;
    //    }
    //    else
    //    {
    //        copyTail->next = cur->next;
    //        copyTail = copyTail->next;
    //    }
    //    cur->next = copyTail->next;
    //    cur = cur->next;
    //}

    return copyHead;
}