数据结构-6-复杂链表复制

﹏ヽ暗。殇╰゛Y 2022-05-27 02:35 151阅读 0赞

#                                     数据结构-6-复杂链表复制 #

复制复杂链表：一个链表的每一个节点，有一个指向下一个节点的next，还有一个指向随机节点或者NULL的random指针。

![这里写图片描述][70]

链表复制起来，很简单，数据复制，链起来就可以了。而这个复杂链表的random复制起来就不容易了。   
在原链表复制过程中，采用复制的新链表的节点链在原节点之后，这样新链表的random就是原链表random->next。

![这里写图片描述][70 1]

// 复杂链表复制 
    #pragma once
    #include<stdio.h>
    #include<Windows.h>
    #include<assert.h>
    
    
    typedef struct ComplexListNode
    {
        int data;
        struct ComplexListNode* next;
        struct ComplexListNode* random;
    }ComplexListNode;
    
    
    void ComplexListPrint(ComplexListNode*list)
    {
        ComplexListNode*cur = list;
        while (cur)
        {
            if (cur->random==NULL)
            {
                printf("%d:NULL", cur->data);
                cur = cur->next;    
            }
            else
            {
                printf("%d:%d ", cur->data,cur->random->data);
                cur = cur->next;
            }
        }
    }
    ComplexListNode* BuyComplexNode(int x)
    {
        ComplexListNode*newnode = (ComplexListNode*)malloc(sizeof(ComplexListNode));
        assert(newnode);
    
        newnode->data = x;
        newnode->next = NULL;
        newnode->random = NULL;
    
        return newnode;
    }
    ComplexListNode* CopyComplexList(ComplexListNode* list);//复杂链表的复制。一个链表的每个节点，有一个指向next指针指向
    //下一个节点，还有一个random指针指向这个链表中的一个随机节点或者NULL，现在要求实现复制这个链表，返回复制后的新链表。
    ComplexListNode* CopyComplexList(ComplexListNode*list)
    {
        ComplexListNode*new = NULL, *tail = NULL;
        //1、逐个复制结点
        ComplexListNode*cur = list;
        if (cur == NULL)
            return NULL;
        while (cur)
        {
            ComplexListNode*newnode = BuyComplexNode(cur->data);
            ComplexListNode*next = cur->next;
    
            cur->next = newnode;
            newnode->next=next;
    
            cur = newnode->next;
        }
    
        //2、置random
        cur = list;
        while (cur)
        {
            ComplexListNode*copy = cur->next;
            if (cur->random == NULL)
            {
                copy->random = NULL;
                cur = cur->next->next;
            }
            else
            {
                copy->random = cur->random->next;
                cur = cur->next->next;
            }
        }
        //3、拆开,分别链起来
        new = tail = list->next;
        list->next = new->next;
        cur = list->next;
        while (cur)
        {
            ComplexListNode*copy=cur->next;
            cur->next = copy->next;
    
            tail->next = copy;
            tail = copy;
    
            cur = cur->next;
        }
        return new;
    }
    
      
       
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        25
        26
        27
        28
        29
        30
        31
        32
        33
        34
        35
        36
        37
        38
        39
        40
        41
        42
        43
        44
        45
        46
        47
        48
        49
        50
        51
        52
        53
        54
        55
        56
        57
        58
        59
        60
        61
        62
        63
        64
        65
        66
        67
        68
        69
        70
        71
        72
        73
        74
        75
        76
        77
        78
        79
        80
        81
        82
        83
        84
        85
        86
        87
        88
        89
        90
        91
        92
        93
        94
        95
        96

//测试部分
    void ComplexListNodeTest()
    {
        ComplexListNode*copylist=NULL;
        ComplexListNode*n1 = BuyComplexNode(1);
        ComplexListNode*n2 = BuyComplexNode(2);
        ComplexListNode*n3 = BuyComplexNode(3);
        ComplexListNode*n4 = BuyComplexNode(4);
    
        n1->next = n2;
        n2->next = n3;
        n3->next = n4;
        n4->next = NULL;
        n1->random = n3;
        n2->random = n1;
        n3->random = n3;
        n4->random = NULL;
        ComplexListPrint(n1);
        printf("\n");
        copylist=CopyComplexList(n1);
        ComplexListPrint(copylist);
    }

[70]: /images/20220527/67626821d02d4f0dba8bdbe6660d87a7.png
[70 1]: /images/20220527/4c1060a9cdae44fba46075b60e5aabbe.png