leetcode No138. Copy List with Random Pointer

本文主要是介绍leetcode No138. Copy List with Random Pointer，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Question:

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.

Algorithm:

算法1：

复制原始链表上的每个结点N创建N',然后把这些创建出来的结点用next连接起来。同时我们把<N,N'>的配对信息放到一个哈希表中。第二步，设置每个结点的random指针，如果在原始链表中结点N的random指向结点S,那么在复制链表中，对应的N'应该指向S'。由于有了哈希表，我们可以用O(1)的时间根据S找到S'。

算法2：

第一步，复制原始链表上的每个结点N创建N'，我们把N'链接在N的后面。

第二步，设置复制出来的结点的random指针。

第三步：把长链表拆分成两个链表

Accepted Code：

算法1：

/*** 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;map<RandomListNode*,RandomListNode*> hash;RandomListNode *pNode=head;RandomListNode *pCloneHead=new RandomListNode(pNode->label);RandomListNode *pCloneNode=pCloneHead;hash[pNode]=pCloneNode;pNode=pNode->next;while(pNode){pCloneNode->next=new RandomListNode(pNode->label);pCloneNode=pCloneNode->next;hash[pNode]=pCloneNode;pNode=pNode->next;}pCloneNode=pCloneHead;pNode=head;while(pCloneNode){pCloneNode->random=hash[pNode->random];pNode=pNode->next;pCloneNode=pCloneNode->next;}return pCloneHead;}
};

算法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;CloneNodes(head);ConnectSiblingNodes(head);return ReconnectNodes(head);}void CloneNodes(RandomListNode* pHead){RandomListNode* pNode=pHead;while(pNode!=NULL){RandomListNode* temp=pNode->next;pNode->next=new RandomListNode(pNode->label);pNode->next->next=temp;pNode=temp;}}void ConnectSiblingNodes(RandomListNode* pHead){RandomListNode* pNode = pHead;while (pNode!=NULL){if (pNode->random == NULL)pNode->next->random = NULL;elsepNode->next->random = pNode->random->next;pNode = pNode->next->next;}}RandomListNode* ReconnectNodes(RandomListNode* pHead){RandomListNode* pNode = pHead;RandomListNode* pCloneHead = NULL;RandomListNode* pCloneNode = NULL;if (pNode){pCloneHead = pNode->next;pCloneNode = pCloneHead;pNode->next = pCloneNode->next;pNode = pNode->next;}while (pNode){pCloneNode->next = pNode->next;pCloneNode = pCloneNode->next;pNode->next = pCloneNode->next;pNode = pNode->next;	}return pCloneHead;}
};

这篇关于leetcode No138. Copy List with Random Pointer的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！