当前位置：首页 > news >正文

[LeetCode]—Copy List with Random Pointer 深度复制带“任意指针”的链表

news 来源：原创 2024/6/25 14:39:17

Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

题目解读：

关键难点：如果只是复制链表，O(n)的复杂度，遍历一遍就完成了。但是，有一个指针random，由于是深度复制，则random要指向相应新节点的位置。那就是题目的考察点所在。

解题：1、先复制链表，然后比对“老链表”逐个对应寻找每个新节点的random指针的指向。时间复杂度为O（N^2）。这显然时间上是不满足题意的。

2、那么考虑，如何才能确定新random的指向呢？如果我们能够通过“老节点”找到对应“新节点”的位置，那么找random的问题就解决了。如图：

我们怎么才能从A找到A‘呢？只能利用节点唯一可用的next指针，将A’连接在A的后面如果上图所示，那么这个关系就确定下来了。找random的问题就解决了。

具体方法：先依次复制所有链表节点，将“新节点”连接在“老节点”后面。并将“新节点”的random设为“老节点”的random值。第二次扫描链表，修正所有“新节点”的random值。

第三次扫描链表，区分开“老链表”和“新链表”形成两个链。时间复杂度为O(N)

注意：1、random是任意指向，有可能是指向NULL的。

2、根据代码通过测试来看，由于是复制，似乎必须不能破坏原始的链表。所以最后需要形成完整的“新链表”和“老链表”。

/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
 
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        if(head==NULL)return NULL;

        RandomListNode *p,*q,*head_new;
        p=head;
        do{
            q=p->next;
            RandomListNode *node=new RandomListNode(p->label);
            p->next=node;
            node->next=q;
            node->random=p->random;
            p=q;
        }while(p!=NULL);

        p=head;
        do{
            q=p->next;
            q->random=(q->random!=NULL)?q->random->next:NULL;
            p=p->next->next;
        }while(p!=NULL);

        head_new=head->next;
        for(p=head,q=head_new;;){
            p->next=q->next;
            p=p->next;
            if(p==NULL)break;
            q->next=p->next;
            q=q->next;
        }

        return head_new;
    }
};