Can anyone tell me what the construct of the last case ? or can somebody help me figure out my bug ?


  • 0
    H

    I've got a WA because of the last case fail to pass.
    OJ gave me thus tips:

    Submission Result: Wrong Answer
    Input: {-1,-1}
    Output: Random pointer of node with label -1 points to a node from the original list.
    Expected: {-1,-1}

    but I cannot figure out where I am wrong.
    my program is as below:

    public RandomListNode copyRandomList(RandomListNode head) {
    	if (head == null) {//0 element
    		return null;
    	}
    	if(head.next == null){//1 element
    		RandomListNode copyHead = new RandomListNode(head.label);
    		copyHead.next = head.next;
    		copyHead.random = head.random;
    		return copyHead;
    	}
    	RandomListNode tail = head;
    	while(tail != null){//shallow copy single node just with label,and linked copy node after original node;
    		RandomListNode copy = new RandomListNode(tail.label);
    		copy.next = tail.next;
    		tail.next = copy;
    		tail = copy.next;
    	}
    	tail = head;
    	while(tail != null){
    		RandomListNode itsCopy = tail.next;
    		itsCopy.random = tail.random == null ? null : tail.random.next;
    		tail = itsCopy.next;
    	}
    	RandomListNode copyTail = head.next;
    	RandomListNode copyHead = copyTail;
    	tail = head;
    	while(copyTail.next != null){
    		tail.next = copyTail.next;
    		tail = tail.next;
    		copyTail.next = tail.next;
    		copyTail = copyTail.next;
    		if(copyTail.next == null){
    			tail.next = null;
    		}
    	}
    	return copyHead;
    }
    

    thanks for you guys


  • 0
    M
    if(head.next == null){//1 element
        RandomListNode copyHead = new RandomListNode(head.label);
        copyHead.next = head.next;
        copyHead.random = head.random;
        return copyHead;
    }
    

    This ends with the copyHead's pointers pointing at the original node, not the copied one. If you passed all the other cases, that is apparently not tested.


  • 0
    H

    thank you very much dude,your answer solved my problem


  • 0
    M
    if(head.next == null){//1 element
        RandomListNode copyHead = new RandomListNode(head.label);
        copyHead.next = head.next;
        copyHead.random = head.random;
        return copyHead;
    }
    

    This ends with the copyHead's pointers pointing at the original node, not the copied one.

    EDIT I had used a comment because I misread the serialization of the list, thinking it was't the case we were looking for. Turns out it was...


Log in to reply
 

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