Why the same algorithm lead to different results?


  • 0
    R

    Below is my accepted code:

    public RandomListNode copyRandomList(RandomListNode head) {
            if (head == null)
    		return null;
    		
    		RandomListNode tracker = head;
    		while(tracker!=null){
    		    RandomListNode temp = new RandomListNode(tracker.label);
    		    RandomListNode next = tracker.next;
    		    tracker.next = temp;
    		    temp.next = next;
    		    tracker = next;
    		}
    		
    		tracker = head;
    		while(tracker!=null){
    		    if(tracker.random!=null)
    		    tracker.next.random = tracker.random.next;
    		    tracker = tracker.next.next;
    		}
    		
                //the part where something may go wrong.
    		tracker = head;
    		RandomListNode copyhead = head.next;
    		while(tracker!=null){
    		    RandomListNode next = tracker.next;
    		    tracker.next = next.next;
    		    if(next.next!=null)
    		    next.next = next.next.next;
    		    tracker = tracker.next;
    		}
    		
    		return copyhead;
     
        }
    

    If I changed the last part, with something like this:

     RandomListNode fakehead = new RandomListNode(0);
        RandomListNode neoNode = fakehead;
        tracker = head;
        while(tracker!=null){
            RandomListNode next = tracker.next;
            tracker.next = next.next;
            neoNode.next = next;
            tracker = tracker.next;
            
        }
        
        return fakehead.next;
    

    Although the algorithm is the same, yet the code above will lead to wrong answer:

    Input:	{-1,1,#,#}
    Output:	{1,#}
    Expected:	{-1,1,#,#}
    

    I could not figure out what went wrong here, can anyone help?

    Thanks.


Log in to reply
 

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