My solution in Java for reference: hashMap way and Node-attached-as-next-node way


  • 1
    J
     // Second way:     Node-attached-as-next-node
    // O(1)time, o(1) space    476ms
    //把相同的放到后一个~这样就不用Hash了 省了空间好棒!
    //缺点是会影响原来的linkedlist
       // Result: 476ms, the time is not reduced much
       //but the original list is modified and has to be  corrected, which is more danderous in real projects.
       // So hashmap is better!
    
    public RandomListNode copyRandomList(RandomListNode head) {
    	RandomListNode first = head, second = null;
    	while (first !=null) {
    		second = new RandomListNode(first.label);
    		second.next =first.next;
    		first.next = second;
    		first = first.next.next;
    	}
    	first = head;
    	while (first !=null) {
    		second = first.next;
    		if (first.random !=null)
    		second.random = first.random.next;
    		first = first.next.next;
    	}
    	first = head;
    	if (head !=null )second = head.next; 
    	head = second;
    	while (first != null) {
    		second = first.next;
    		first.next = second.next;
    		if (second.next !=null)
    		second.next = second.next.next;
    		first = first.next;
    		second = second.next;
    	}
    	return head;
    	
    }
    
    
    
    
        // First way: HashMap  546 MS
        // O(1) time, o(1) space
        //Better way! (* ̄︶ ̄)y
    
     public RandomListNode copyRandomListByHash(RandomListNode head) {
            RandomListNode sec=null, pre=null, head2 = null, cur = head;
            Map<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
            // normal copy
            while (cur != null) {
                sec = new RandomListNode(cur.label);
                if (pre != null) {
                    pre.next = sec;
                }
                else head2 = sec;
                map.put(cur,sec);
                pre = sec;
                cur = cur.next;
            }
            // ramdompointer copy
            sec = head2;
            while (head != null) {
                if (map.containsKey(head.random)) {
                    sec.random = map.get(head.random);
                }
                head = head.next;
                sec = sec.next;
            }
            return head2;
            
            
            
        }

  • 0
    S

    Appreciate this great solution sharing. Can you translate your comment? Discuss is English only.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.