题目描述
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.
The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:
- val: an integer representing Node.val
- random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.
Example1:
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
Example2:
Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]
Example3:
Input: head = []
Output: []
Explanation: Given linked list is empty (null pointer), so return null.
解题思路
- 三个步骤，首先是复制每个节点
- 然后复制random指针
- 最后拆分成两个节点
C++代码
/*
// 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;
}
copyLinkList(head);
copyRandomPoint(head);
return splitLinkList(head);
}
void copyLinkList(Node* head){
Node* pNode = head;
while(pNode != NULL){
Node* copyNode = new Node(pNode -> val);
copyNode -> val = pNode -> val;
copyNode -> next = pNode -> next;
copyNode -> random = NULL;
pNode -> next = copyNode;
pNode = copyNode -> next;
}
}
void copyRandomPoint(Node* head){
Node* pNode = head;
while(pNode != NULL){
if(pNode -> random != NULL){
pNode -> next -> random = pNode -> random -> next;
}
pNode = pNode -> next -> next;
}
}
Node* splitLinkList(Node* head){
Node* pNode = head;
Node* copyHead = NULL, *copyNode = NULL;
if(pNode != NULL){
copyHead = pNode -> next;
copyNode = pNode -> next;
pNode -> next = copyNode -> next;
pNode = pNode -> next;
}
while(pNode != NULL){
copyNode -> next = pNode -> next;
copyNode = copyNode -> next;
pNode -> next = copyNode -> next;
pNode = pNode -> next;
}
return copyHead;
}
};
