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 representingNode.val
random_index
: the index of the node (range from0
ton-1
) where random pointer points to, ornull
if it does not point to any node.
Example 1:
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]] Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
Example 2:
Input: head = [[1,1],[2,1]] Output: [[1,1],[2,1]]
Example 3:
Input: head = [[3,null],[3,0],[3,null]] Output: [[3,null],[3,0],[3,null]]
Example 4:
Input: head = [] Output: [] Explanation: Given linked list is empty (null pointer), so return null.
Constraints:
-10000 <= Node.val <= 10000
Node.random
is null or pointing to a node in the linked list.- Number of Nodes will not exceed 1000.
A:
啊啊啊啊啊啊,终于明白了。这个题目考点在于 random有可能是指向后面的节点。如果仅仅是通常的copy的话,无法当即设置random 指针。 --------因此可以用map
/* // 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) { unordered_map<Node*, Node*> M; Node* header = new Node(2); Node* tailnew = header; Node *tailold = head; while(tailold){ Node * tmp = new Node(tailold->val); tailnew ->next = tmp; tailnew = tailnew->next; M[tailold] = tmp; tailold = tailold->next; } tailold = head; tailnew = header->next; while(tailnew){ tailnew->random = M[tailold->random]; tailnew = tailnew->next; tailold = tailold->next; } return header->next; } };
Learned:
-------------------------------Third time --------------------
travel the list two pass ,
Pass 1: create the list and insert right after that node,
Pass 2: set up the random node
Pass 3: detach the copied node list.
(As Pass 2 and Pass 3 can do together, we thus need only two pass.)
Correction !!!!!!!!!!!
Pass 2 and Pass 3 can NOT do together.
public class Solution { public RandomListNode copyRandomList(RandomListNode head) { if(head == null) return null; RandomListNode runner = head; while(runner != null){ RandomListNode tmp = new RandomListNode(runner.label); tmp.next = runner.next; runner.next = tmp; runner = tmp.next; } // set the random label runner = head; while(runner != null ){ // && runner.next != null){ if(runner.random != null) runner.next.random = runner.random.next; runner = runner.next.next; } // detach RandomListNode newHeader = new RandomListNode(100000000); runner = head; RandomListNode newTail = newHeader; while(runner != null && runner.next != null){ //detach the next one newTail.next = runner.next; newTail = newTail.next; runner.next = runner.next.next; runner = runner.next; } return newHeader.next; } }
No comments:
Post a Comment