LeetCode-138 复制带随机指针的链表

本文为LeetCode 138 复制带随机指针的链表的题解。

LeetCode 138题目链接

题目大意

一个链表，定义如下

class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};

除了常规的val值和next指针，还有一个random指针，该指针可以指向链表中的任何节点或空节点。

要求对该链表进行 深拷贝。深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

题目难点

如果只是常规地复制链表，很容易就能实现。该题不同之处在于每个节点有一个random指针，它可能指向任意的一个节点，可能指向前面也可能指向后面，在目前还没有初始化的节点，所以对于random指针的处理是本题的关键

解题思路

方法一 Map

利用C++ STL的Map记录每个节点的random指针，先复制不带有random指针的链表，之后再利用Map重新构成带有random指针的链表。

方法二 在原节点的基础上修改

在链表的每个节点后面新建一个节点，新节点和该节点一样，然后旧节点指向新节点，新节点的next等于原先旧节点的next，这样直接在新节点上修改，random指针也很方便。

代码

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head==NULL)return NULL;
        Node*p=head,*q;
        while(p){
            q=p->next;
            p->next=new Node(p->val);
            p->next->next=q;
            p=q;
        }
        p=head;
        while(1){
            if(p->random)
                p->next->random=p->random->next;
            if(p->next->next) p=p->next->next;
            else break;
        }
        p=head;q=head->next;
        Node *ret=head->next;
        while(p&&q){
            p->next=q->next;
            p=p->next;
            if(p)q->next=p->next;
            else break;
            q=q->next;
        }
        return ret;    
    }
};

解题总结

题目其实不难，方法一可能是比较常见的思路，方法二比较巧妙，在长度为n的链表里每个节点再新建一个节点，使其长度达到2n，这样可以方便地对使用旧节点的数据，也可以修改新节点的值，操作起来比较方便，而且也可以选择性地保留节点。