发布日期: 2024-02-21

JZ35复杂链表的复制

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）。下图是一个含有5个结点的复杂链表。图中实线箭头表示next指针，虚线箭头表示random指针。为简单起见，指向null的指针没有画出。

jz35-图1

示例:

输入:{1,2,3,4,5,3,5,’#’,2,’#’}

输出:{1,2,3,4,5,3,5,’#’,2,’#’}

解析:我们将链表分为两段，前半部分{1,2,3,4,5}为ListNode，后半部分{3,5,‘#’,2,‘#’}是随机指针域表示。

以上示例前半部分可以表示链表为的ListNode:1->2->3->4->5

后半部分，3，5，’#‘，2，‘#’分别的表示为

1的位置指向3，2的位置指向5，3的位置指向null，4的位置指向2，5的位置指向null

如下图:

jz35-图2

示例1

输入：

{1,2,3,4,5,3,5,#,2,#}

返回值：

{1,2,3,4,5,3,5,#,2,#}

方法一：建立映射表

完全新建一个链表，建立映射表mymap,节点A的克隆节点为A’,节点B的克隆节点为B’,A的random指针指向B，则A’的random指针指向B’,

即mymap[A]=A’,A’->random=mymap[A->random];

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {//建立映射表（基本）
public:
    RandomListNode* Clone(RandomListNode* pHead) {

        if(pHead==nullptr)return nullptr;
        RandomListNode* curhead=pHead;
        RandomListNode* entry=new RandomListNode(0);
        RandomListNode* curcloentry=entry;
        map<RandomListNode*,RandomListNode*>mymap;
        while(curhead!=nullptr){             //建立映射表
        RandomListNode* newHead=new RandomListNode(curhead->label);
        mymap[curhead]=newHead;
        curcloentry->next=newHead;
        curhead=curhead->next;
        curcloentry=curcloentry->next;
        }
        
        curhead=pHead;
        RandomListNode* clohead=mymap[curhead];
        while(curhead!=nullptr){            //克隆链表节点之间的指针按照映射表来指向对应节点
           clohead->random=mymap[curhead->random];
           clohead=clohead->next;
           curhead=curhead->next;
        }
        return entry->next;
    }
};

方法二：利用链表前后链接关系确认克隆后random指针的指向,省去了映射表的建立

将克隆后的节点插入到原节点之后，A->A’->B->B’->C->C’,

jz-35图3

A’=A->next, A’->random=A->random->next;

确认克隆后的random指针指向后再分离原链表和克隆链表

class Solution {//先在每一个节点后面附它的克隆节点（定位），克隆节点的random指向本体random指向节点的next节点,克隆节点的random指到位后，将克隆链表与原链表剥离
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        if(pHead==nullptr)return nullptr;
        RandomListNode* curHead=pHead;
        while(curHead!=nullptr){//每一个节点后附上它的克隆
            RandomListNode* cloNode=new RandomListNode(curHead->label);
            cloNode->next=curHead->next;
            curHead->next=cloNode;
            curHead=cloNode->next;
        }

        curHead=pHead;
        while(curHead!=nullptr){//克隆节点的random指针根据定位指向相应位置
           if(curHead->random!=nullptr)curHead->next->random=curHead->random->next;
           curHead=curHead->next->next;
        }

        curHead=pHead;
        RandomListNode *cloHead=pHead->next;
        RandomListNode *curcloHead=cloHead;
        while(curHead!=nullptr){//分离两个链表
            if(curHead->next!=nullptr){
              curHead->next=curHead->next->next;
            }
            if(curcloHead->next!=nullptr){
               curcloHead->next=curcloHead->next->next;
            }
            curHead=curHead->next;
            curcloHead=curcloHead->next;
        }
        return cloHead;
    }
};