Simple java solution O(1) space, O(n) time complexity:)


  • 4
    S
     public RandomListNode copyRandomList(RandomListNode head) {
            if (head == null) {
                return head;
            }
    
            RandomListNode cur = head;
            RandomListNode next = null;
            while(cur != null) { //insert a new node between originals
                next = cur.next;
                cur.next = new RandomListNode(cur.label);
                cur.next.next = next;
                cur = next;
            }
            
            RandomListNode copyHead = head.next;
            cur = head;
            while(cur != null) { //set the random of each newNode
                if(cur.random == null) {
                    cur.next.random = null;
                }
                else {
                    cur.next.random = cur.random.next;
                }
                cur = cur.next.next;
            }
    
    
            cur = head;
            RandomListNode curCopy = null;
            while(cur != null && cur.next != null) { // set the next of each original and new node
                curCopy = cur.next;
                cur.next = cur.next.next;
                cur = curCopy;
            }
    
            return copyHead;
        }

  • 0
    O

    Brilliant idea! I really like it.


Log in to reply
 

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