复杂链表的复制

问题：一个链表的每个节点，有一个指向next指针指向下一个节点，还有一个random指针指向这个链表中的一个随机节点或者NULL，现在要求复制这个链表

 

• 要复制的链表样例

• 思路

1. 遍历整个链表，复制节点，将新节点插到老节点的后边
2. 遍历整个链表的老节点，复制random字段
3. 将老链表拆成新链表和老链表

 

• 定义结构体

#include <stdlib.h>
#include <stdio.h>

typedef struct CLNode
{
	int data;
	struct CLNode* random;
	struct CLNode* next;
}   CLNode;

• 创建新节点

static CLNode * ComplexCreateNode(int data)
{
	CLNode *node = (CLNode *)malloc(sizeof(CLNode));
	node->data = data;
	node->random = NULL;
	node->next = NULL;

	return node;
}

• 复制复杂链表

CLNode* CopyCmList(CLNode* list)
{
    //复制节点
    CLNode* cur = list;
    while(cur != NULL)
    {
        CLNode* newnode = ComplexCreateNode(cur->data);
        newnode->next = cur->next;
        cur->next = newnode;
        
        cur = cur->next->next;
    }
    
    //复制random
    cur = list;
    while(cur != NULL)
    {
        cur->next->random = cur->random->next;
        
        cur = cur->next->next;
    }
    
    //拆分
    cur = list;
    CLNode* newlist = cur->next;  //保存新链表
    while(cur != NULL)
    {
        CLNode* node = cur->next;
        cur->next = node->next;
        if(cur->next != NULL)
        {
            node->next = cur->next->next;
        }
        else
        {
            node->next = NULL;
        }
        
        cur = cur->next;
    }
    return newlist;
}