My solution in java


  • 0
    R
    /**
     * Definition for singly-linked list with a random pointer.
     * class RandomListNode {
     *     int label;
     *     RandomListNode next, random;
     *     RandomListNode(int x) { this.label = x; }
     * };
     */
    public class Solution {
        public RandomListNode copyRandomList(RandomListNode head) {
            
    		RandomListNode tmp = head;
    
    		while (tmp != null) {
    			RandomListNode newHead = new RandomListNode(tmp.label);
    			newHead.next = tmp.next;
    			newHead.random = null;
    			tmp.next = newHead;
    			tmp = newHead.next;
    		}
    
    		tmp = head;
    		while (tmp != null && tmp.next != null) {
    			RandomListNode tmpNext = tmp.next;
    			RandomListNode random = tmp.random;
    			RandomListNode next = random == null ? null : random.next;
    			tmpNext.random = next;
    			tmp = tmpNext.next;
    		}
    		return split(head);
            
        }
        
        private RandomListNode split(RandomListNode head) {
    		if (head == null) {
    			return null;
    		}
    
    		RandomListNode origHead = head;
    		RandomListNode newHead = head.next;
    
    		RandomListNode origTmp = origHead;
    		RandomListNode newTmp = newHead;
    
    		while (origTmp != null && newTmp != null) {
    			origTmp.next = newTmp.next;
    			origTmp = origTmp.next;
    			if (origTmp != null) {
    				newTmp.next = origTmp.next;
    				newTmp = newTmp.next;
    			}
    		}
    		return newHead;
    
    	}
    }

Log in to reply
 

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