LeetCode138：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.

解题思路：

拷贝链表时，新节点的random指针不太好设置，因为是随机的，所以如果采用常规方法，必须每设置一个新节点的random指针时，必须到两链表中进行查找。

这里，我采用了一些小技巧，当拷贝一个新节点时，将该新节点连接到原节点的后面

第一步做完后，遍历链表，设置拷贝节点的random指针，设置拷贝节点的random指针时，可根据原节点的random指针进行设置，因为原节点的random指向的节点的下一个节点即为拷贝节点额random要指向的节点。

最后，将链表进行分离即可。

实现代码：

#include <iostream>

using namespace std;

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 = head;

        while(p)

        {

            RandomListNode *node = new RandomListNode(p->label);//拷贝一个新节点，然后将该新节点链接到原节点的后面

            node->next = p->next;

            p->next = node;

            p = node->next;

        }

        p = head;

        while(p)//根据原节点设置新节点的random指针

        {

            if(p->random)//如果原节点的random指针不为空则设置拷贝节点

            {

                //拷贝节点的random指针指向的节点可利用原节点的random指针找到，

                //因为每个拷贝节点都在原节点的下一个节点

                p->next->random = p->random->next;

            }

            p = p->next->next;

        }

        //将原链表和新建链表进行分离

        RandomListNode *chead = head->next;

        head->next = head->next->next;

        RandomListNode *q = chead;

        head = head->next;

        while(head)

        {

            q->next = head->next;

            head->next = head->next->next;

            head = head->next;

            q = q->next;

        }

        return chead;

    }

};

int main(void)

{

    return ;

}

巴特西

LeetCode138：Copy List with Random Pointer

最新文章

热门文章