数据结构之链表面试题：复杂链表的复制

话不多说直接上代码，如果有什么问题请在后台留言，必回，谢谢支持

#pragma once

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int DataType;

typedef struct ComplexListNode
{
    DataType _data;
    struct ComplexListNode* _next;
    struct ComplexListNode* _random; //_random指向这个链表中的一个随机节点或者NULL，
}ComplexListNode, *pComplexListNode;

//复杂链表的初始化
ComplexListNode* BuyComplexListNode(DataType x);
//拷贝原复杂链表
ComplexListNode* CopyComplexListNode(pComplexListNode pHead);
//打印链表
void PrintComplexListNode(pComplexListNode pHead);


//复杂链表的初始化
ComplexListNode* BuyComplexListNode(DataType x)
{
    pComplexListNode pNewComplexListNode = (ComplexListNode*)malloc(sizeof(ComplexListNode));
    if (NULL == pNewComplexListNode)
    {
        pNewComplexListNode->_data = x;
        pNewComplexListNode->_next = NULL;
        pNewComplexListNode->_random = NULL;
    }
    return pNewComplexListNode;
}
//拷贝原复杂链表
ComplexListNode* CopyComplexList(pComplexListNode pHead)
{
    pComplexListNode pOldNode = pHead;
    pComplexListNode pNewNode = NULL;
    if (NULL == pHead)
        return NULL;
    //原链表每个节点后插入值相同的节点
    while (pOldNode)
    {
        pNewNode = (pComplexListNode)malloc(sizeof(ComplexListNode));
        if (NULL==pNewNode)
        {
            pNewNode->_next = pOldNode;
            pOldNode->_next = pNewNode;
            pOldNode = pNewNode->_next;
        }
    }
    //给新插入节点的随机指针域赋值
    pOldNode = pHead;
    while (pOldNode)
    {
        pNewNode = pOldNode->_next;
        if (NULL == pOldNode->_random)
            pNewNode->_random = NULL;
        else
            pNewNode->_random = pOldNode->_random->_next;
        pOldNode = pNewNode->_next;
    }
    //将新插入的链表从原链表中分离
    pOldNode = pHead;
    pNewNode = pOldNode->_next;
    while (pOldNode)
    {
        pNewNode = pOldNode->_next;
        pOldNode->_next = pNewNode->_next;
        pOldNode = pNewNode;
    }
}
//打印链表
void PrintComplexListNode(pComplexListNode pHead)
{
    assert(pHead);
    pComplexListNode pCur = pHead;
    while (pCur)
    {
        if (NULL == pCur->_random)
        {
            printf("%d:NULL->\n",pCur->_data);
        }
        else
        {
            printf("%d:%d\n",pCur->_data,pCur->_random->_data);
        }
        pCur = pCur->_next;
    }
}