复杂链表的复制（链表的每个结点，有一个next指针指向下一个结点，还有一个random指针指向这个链表中的一个随机结点或者NULL）

举一个复杂链表的例子：


首先我们需要创建一个复杂链表：
  1. 要创建链表首先需要一个结构体：（结构体成员须包括数据，next指针，以及random指针）

typedef struct node{
    DataType data;
    struct node* next;
    struct node* random;
}Clinklist;

1. 创建如上图所示的复杂链表

    Clinklist node1, node2, node3, node4;
    Clinklist *chead=&node1;

    node1.data = 1;
    node1.next = &node2;
    node1.random = &node3;

    node2.data = 2;
    node2.next = &node3;
    node2.random = &node1;

    node3.data = 3;
    node3.next = &node4;
    node3.random = &node3;

    node4.data = 4;
    node4.next = NULL;
    node4.random = NULL;

复杂链表的复制

1. 先处理复杂链表为空的情况。 链表若为空，则直接返回。
2. 若复杂链表不为空。想要复制链表，首先在原链表的每个结点后边插入值相等的新结点。

3. 给新结点的随机指针域复制。由图可见：新结点的随机指针域 是 原结点随机指针域 的下一个结点。
即就是pnewnode->random=pcur->random->next;
4. 将复制完成的新结点从原结点中拆下。

复杂链表复制

//复杂链表的复制
Clinklist *CopyComplexlist(Clinklist *chead)
{
    Clinklist *pcur = NULL;
    Clinklist *pnewnode = NULL;
    Clinklist *pnode = NULL;


    //1.处理复杂链表为空的情况
    if (chead == NULL)
    {
        return NULL;
    }
    //2. 复杂链表不为空的情况
    //a. 在原链表的每个节点后插入值相等的新节点

    pcur = chead;
    while (pcur)
    {
        pnewnode = (Clinklist *)malloc(sizeof(Clinklist));
        if (pnewnode == NULL)
        {
            return NULL;
        }
        pnewnode->data = pcur->data;

        pnewnode->next = pcur->next;
        pcur->next = pnewnode;

        pcur = pnewnode->next;
    }
    //记住头结点方便返回
    pnode = chead->next;

    //b.给新结点的随机指针域赋值
    pcur = chead;
    while (pcur != NULL)
    {
        pnewnode = pcur->next;
        if (pcur->random == NULL)
        {
            pnewnode->random = NULL;
        }
        else
        {
            pnewnode->random = pcur->random->next;
        }
        pcur = pnewnode->next;
    }
    //c.将新节点从原链表中拆下

    pcur = chead;
    pnewnode = chead->next;

    while (pnewnode != NULL)
    {
        pcur->next = pnewnode->next;
        pcur = pnewnode;
        pnewnode = pnewnode->next;
    }
    pcur->next = pnewnode;

    return pnode;
}