010、随机链表复制

0、题目描述

随机链表复制

1、法1

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */

struct Node* BuyNewNode(int val)
{
    struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));
    newnode->val = val;
    newnode->next = NULL;
    newnode->random = NULL;
    return newnode;
}

struct Node* copyRandomList(struct Node* head) 
{
    if (head == NULL)
        return NULL;
	struct Node* cur = head;
    struct Node* newnode = NULL;
    struct Node* next = NULL;
    //把每个节点放在原节点的后面
    while (cur)
    {
        next = cur->next;
        newnode  = BuyNewNode(cur->val);
        cur->next = newnode;
        newnode->next = next;
        cur = next;
    }
    
    cur = head;
    struct Node* newlist = cur->next;
    struct Node* newcur = newlist;
    while (cur)
    {
        //复制节点的random，上一个节点random的next
        if (cur->random == NULL)
        {
            newcur->random = NULL;
        } 
        else
        {
            newcur->random = cur->random->next;
        }
        
        //复制完random之前不能动cur->next
        
        cur = cur->next->next;
        if (cur)
            newcur = newcur->next->next;
    }

    //解开
    cur = head;
    newcur = newlist = cur->next;
    while (cur)
    {
        cur->next = newcur->next;
        cur = cur->next;
        if (cur)
        {
            newcur->next = cur->next;
            newcur = newcur->next;
        }
    }
    return newlist;
}