C语言|Leetcode 138.随机链表的复制

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

typedef struct Node Node;
struct Node* copyRandomList(struct Node* head) 
{
    //拷贝节点插入到原链表
    if(head == NULL)
    {
        return NULL;
    }
    Node* cur = head;
    while(cur)
    { 
        Node* copynode = (Node*)malloc(sizeof(Node));
        copynode->val = cur->val;

        copynode->next = cur->next;
        cur->next = copynode;

        cur = copynode->next;
    }

    //链接random
    cur = head;
    while(cur)
    {
        Node* copynode = cur->next;
        if(cur->random == NULL)
        {
            copynode->random = NULL;
        }
        else
        {
            copynode->random = cur->random->next;
        }
        cur = copynode->next;
        
    }
    
    //将复制链表剪下来
    cur = head;
    Node* newhead = NULL, *newtail = NULL;
    while(cur)
    {
      Node* copynode = cur->next;
      Node* next = copynode->next;
      if(newtail == NULL)
      {
         newhead = newtail = copynode;
      }
      else
      {
        newtail->next = copynode;
        newtail  = copynode;
      }
      cur = next;
    }
    return newhead;
}