Sharing Java O(n) and no Collection solution


  • 3
    L

    Take 1->2->3 as an example(Runtime: 347 ms):

    /**
     * Step 1: duplicate each nodes, 1->2->3 becomes 1->`1->2->`2->3->`3;
     * Step 2: copy node's random according the previous node;
     * Step 3: split the list into two
     */
    public RandomListNode copyRandomList(RandomListNode head) {
        if(head==null)  return null;
    
        // step1: 1->2->3 become 1->`1->2->`2->3->`3
        RandomListNode cur = head;
        while (cur!=null){
            RandomListNode newNode = new RandomListNode(cur.label);
            newNode.next = cur.next;
            cur.next = newNode;
            cur = newNode.next;
        }
    
        // step2: copy random
        cur = head;
        while(cur!=null){
            RandomListNode newCur = cur.next;
            newCur.random = (cur.random==null) ? null : cur.random.next;
            cur = newCur.next;
        }
    
        // step3: split
        RandomListNode newHead = head.next;
        cur = head;
        while(cur!=null){
            RandomListNode newCur = cur.next;
            cur.next = newCur.next;
            newCur.next = (cur.next!=null) ? cur.next.next : null;
            cur = cur.next;
        }
    
        return newHead;
    }

Log in to reply
 

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