LeetCode, LintCode - Copy a linked list with next and arbit pointer - GeeksforGeeks

https://xuezhashuati.blogspot.com/2017/03/lintcode-105-copy-list-with-random.html
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.


Challenge
Could you solve it with O(1) space?


思路
1：遍历一遍，每一个节点后面插入一个复制的节点，不考虑random pinter。
a -> b -> c -> null 变成 a -> a -> b -> b -> c -> c -> null

2：遍历一遍，每到一个复制的节点，更新random pointer。

3：遍历一遍，恢复原链表，并把复制节点加入新链表。
a -> b -> c -> null
dummy -> a -> b -> c -> null

4：返回新链表。
a -> b -> c -> null

 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };

    public RandomListNode copyRandomList(RandomListNode head) {        
        RandomListNode iter;
        RandomListNode next;
        iter = head;
        
        while (iter != null) {
            next = iter.next;
            RandomListNode copy = new RandomListNode(iter.label);
            iter.next = copy;
            copy.next = next;
            iter = next;
        }
        
        iter = head;
        while (iter != null) {
            if (iter.random != null) {
                iter.next.random = iter.random.next;
            }
            iter = iter.next.next;
        }
        
        RandomListNode dummy = new RandomListNode(0);
        iter = head;
        RandomListNode copyIter;
        RandomListNode copy;
        copyIter = dummy;
        while (iter != null) {
            next = iter.next.next;
            
            copy = iter.next;
            copyIter.next = copy;
            copyIter = copy;
            
            iter = next;
        }
        
        return dummy.next;
    }

Solution from EPI

  public static PNode<Integer> copyPostingsList(PNode<Integer> l) {
    // Return empty list if l is nullptr.
    if (l == null) {
      return null;
    }

    // 1st stage: Copy the nodes from l.
    PNode<Integer> p = l;
    while (p != null) {
      PNode<Integer> temp = new PNode<>(p.data, p.next, null);
      p.next = temp;
      p = temp.next;
    }

    // 2nd stage: Update the jump field.
    p = l;
    while (p != null) {
      if (p.jump != null) {
        p.next.jump = p.jump.next;
      }
      p = p.next.next;
    }

    // 3rd stage: Restore the next field.
    p = l;
    PNode<Integer> copied = p.next;
    while (p.next != null) {
      PNode<Integer> temp = p.next;
      p.next = temp.next;
      p = temp;
    }
    return copied;
  }
 Method 1 (Uses O(n) extra space)

This method stores the next and arbitrary mappings (of original list) in an array first, then modifies the original Linked List (to create copy), creates a copy. And finally restores the original list.

1) Create all nodes in copy linked list using next pointers.
3) Store the node and its next pointer mappings of original linked list.
3) Change next pointer of all nodes in original linked list to point to the corresponding node in copy linked list.
Following diagram shows status of both Linked Lists after above 3 steps. The red arrow shows arbit pointers and black arrow shows next pointers.

Figure 2

4) Change the arbit pointer of all nodes in copy linked list to point to corresponding node in original linked list.
5) Now construct the arbit pointer in copy linked list as below and restore the next pointer of nodes in the original linked list.

       copy_list_node->arbit =
                      copy_list_node->arbit->arbit->next;
       copy_list_node = copy_list_node->next; 

6) Restore the next pointers in original linked list from the stored mappings(in step 2).

Time Complexity:  O(n)
Auxiliary Space:  O(n)

Method 2 (Uses Constant Extra Space)
Thanks to Saravanan Mani for providing this solution. This solution works using constant space.
1) Create the copy of node 1 and insert it between node 1 & node 2 in original Linked List, create the copy of 2 and insert it between 2 & 3.. Continue in this fashion, add the copy of N afte the Nth node
2) Now copy the arbitrary link in this fashion

     original->next->arbitrary = original->arbitrary->next;  /*TRAVERSE 
TWO NODES*/

This works because original->next is nothing but copy of original and Original->arbitrary->next is nothing but copy of arbitrary.
3) Now restore the original and copy linked lists in this fashion in a single loop.

     original->next = original->next->next;
     copy->next = copy->next->next;

4) Make sure that last element of original->next is NULL.

Time Complexity: O(n)
Auxiliary Space: O(1)

Read full article from Copy a linked list with next and arbit pointer | GeeksforGeeks