Fast and elegant Java solution with explanation


  • 0
    L
     public RandomListNode copyRandomList(RandomListNode head)
      {
        // ex. 1.random->3
        // 1.next->2
        // 2.random->1
        // 2.next=3
        if (head == null)
        {
          return null;
        }
        RandomListNode iter = head;
        // pass#1.
        //In this iteration we will insert intermediate nodes or more like a prime. 
       //So 1->2->3 becomes 1->1'->2->2'->3->3'. Don't worry about random yet.
        while (iter != null)
        {
          RandomListNode next = iter.next;
          iter.next = new RandomListNode(iter.label);
          iter.next.next = next;
          iter = next;
        }
        // pass#2.
        iter = head;
       //Take care of the random pointer. The random of 1 should be pointed out to 1' and so on. Ex. if 1 had a random pointer to 2, we will do a random pointer from 1' to 2' in this step.
        while (iter != null && iter.next != null)
        {
          RandomListNode random = iter.random;
          if (random != null)
          {
            iter.next.random = random.next;
          }
          iter = iter.next.next;
        }
        // pass#3.
        iter = head;
        RandomListNode newListHead = iter.next;
        // 1->1'->2->2'->3->3'
       //Restore the list by making sure that every alternate pointer points to the the right one. 
        while (iter != null && iter.next != null)
        {
          RandomListNode temp = iter.next;
          iter.next = temp.next;
          iter = temp;
        }
        return newListHead;
      }
    

Log in to reply
 

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