[Leetcode]138. Copy List with Random Pointer

本文主要是介绍[Leetcode]138. 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.

解法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 == nullptr) return head;RandomListNode *p = head;while (p != nullptr) {RandomListNode *pCloned = new RandomListNode(p->label);pCloned->next = p->next;p->next = pCloned;p = pCloned->next;}p = head;while (p != nullptr) {if (p->random != nullptr)p->next->random = p->random->next;p = p->next->next;}p = head;RandomListNode *pCloneHead = head->next, *pCloned = head->next;while (p != nullptr) {p->next = p->next->next;if (pCloned->next != nullptr)pCloned->next = pCloned->next->next;p = p->next;pCloned = pCloned->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) {RandomListNode *p = nullptr, *pCloned = nullptr, *pClonedHead = nullptr;map<RandomListNode*, int> mp;int pos = 0;for (p = head; p != nullptr; p = p->next) {mp[p] = pos++;}vector<RandomListNode*> vec;for (p = head; p != nullptr; p = p->next) {RandomListNode *node = new RandomListNode(p->label);vec.push_back(node);if (pClonedHead == nullptr) {pClonedHead = node;pCloned = node;}else {pCloned->next = node;pCloned = node;}}for (pCloned = pClonedHead, p = head; pCloned != nullptr && p != nullptr; p = p->next, pCloned = pCloned->next) {if (p->random != nullptr) {pos = mp[p->random];pCloned->random = vec[pos];}}return pClonedHead;}
};

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

---