Friday, October 4, 2013

138. Copy List with Random Pointer ----M

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.

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