# # 138 Copy List with Random Pointer

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**](https://en.wikipedia.org/wiki/Object_copying#Deep_copy) of the list.

**Example 1:**

![](https://discuss.leetcode.com/uploads/files/1470150906153-2yxeznm.png)

```
Input:
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}

Explanation:
Node 1's value is 1, both of its next and random pointer points to Node 2.
Node 2's value is 2, its next pointer points to null and its random pointer points to itself.
```

**Note:**

1. You must return the **copy of the given head** as a reference to the cloned list.

這題是要複製一個linked list。

如 : head linked list &#x20;

```java
 memory:  0x11   0x88  
                  __
                 |  |
                 r  ↓
 head     ◇→→→   ◇→→→   null
          r      ↑
          |______|
          
  next:    0x88  null
  random:  0x88  0x88 
  val:     1      2     
  
  原題目裡的輸入:
  {"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}
  
  我轉成如下:
  {"$id":"1",
	"next":
		{"$id":"2",
			"next":null,
			"random":{"$ref":"2"},
			"val":2},
	"random":{"$ref":"2"},
	"val":1}
	
  你要回傳:
 memory:  0xa8   0x93  
                  __
                 |  |
                 r  ↓
 newlist  ◇→→→   ◇→→→   null
          r      ↑
          |______|
          
  next:    0x93  null
  random:  0x93  0x93 
  val:     1      2     
 
 
```

這裡可以有一個方式就是直接建一個新的，但因為原Node裡的random指的可能是下一個Node，或是下下個Node，這裡要注意的是，參考也是要指向新的Node。個人做法是先用一個while 迴圈把原來head linked list的next給new出來給新的n listed list。再用一個while迴圈處理random。但因random是某個next Node，但重點是要給他新linked list 的參考，而不是給head linded list 的參考。

程式碼:

```java
class Solution {
    public Node copyRandomList(Node head) {
       if(head == null){
            return head;
        }
        Node t = new Node(head.val, null, null);
        Node n = t;
        Node h = head;
        while(head != null){
            Node ne = null;
            if(head.next != null){
                 ne =  new Node(head.next.val, head.next.next, null);
                t.next = ne;
            }
            t = t.next;
            head = head.next;
        }
        
        head = h;
        t = n;
        while(head != null){
            if(head.random != null){
                Node tempN = n;
                      while(n != null){
                        if(n.val == head.random.val){
                            t.random = n;
                        }
                        n = n.next;
                        }
                    n = tempN;
            }
            t = t.next;
            head = head.next;
        }
        return n;
    }
}
```

這個做是正確的，但時間秏很多，因為每一個Noded的random會要重新遍尋整個n list。

該題還有另一個比省時間的做法，就是在原來的Node的下一個複製一個一樣的copy的Node。

分三次，第一次是在head linked list 的每一個Node的下一個COPY一個一樣val的Node

```java
memory:   0x11   0x88  
                  __
                 |  |
                 r  ↓
 head     ◇→→→   ◇→→→   null
          r      ↑
          |______|
          
  next:    0x88  null
  random:  0x88  0x88 
  val:     1      2    
  
  
  while run one:
 memory:  0x11  0x25  0x88  
                         ___
                         | |
                         r ↓
 head     ◇→→→   ◇→→→   ◇→→→   null
          r             ↑
          |_____________|
          
  next:    0x25  0x88  null
  random:  0x88  null  0x88
  val:     1      1     2
  
  
  while run two:
  memory:  0x11  0x25  0x88   0xb5
                         ___
                         | |
                         r ↓
 head     ◇→→→   ◇→→→   ◇→→→  ◇→→→ null
          r             ↑
          |_____________|
          
  next:    0x25  0x88   0xb5   null
  random:  0x88  null   0x88   null
  val:     1      1     2      2
  
```

第二部分:將COPY的Node裡的random指向新的copy Node，也就是0x25 Node 及 0xb5的Node的random要指向新的COPY的Node 0xb5

```java
memory:  0x11  0x25  0x88   0xb5
                         ___
                         | |
                         r ↓
 head     ◇→→→   ◇→→→   ◇→→→  ◇→→→ null
          r             ↑
          |_____________|
          
  next:    0x25  0x88   0xb5   null
  random:  0x88  null   0x88   null
  val:     1      1     2      2
  
  while run once:
  memory:  0x11  0x25  0x88   0xb5
                 ______________
                 |            |
                 |      ___   |
                 |      | |   |
                 r      r ↓   ↓
 head     ◇→→→   ◇→→→   ◇→→→  ◇→→→ null
          r             ↑
          |_____________|
          
  next:    0x25  0x88   0xb5   null
  random:  0x88  0xb5   0x88   null
  val:     1      1     2      2
  
  while run two:
 memory:  0x11  0x25  0x88   0xb5
                 ______________
                 |            |
                 |      ___   |
                 |      | |   |
                 r      r ↓   ↓
 head     ◇→→→   ◇→→→   ◇→→→  ◇→→→ null
          r             ↑     r  ↑
          |_____________|     |__|
                   
          
  next:    0x25  0x88   0xb5   null
  random:  0x88  0xb5   0x88   0xb5
  val:     1      1     2      2
 
```

第三部分，就是新的Node指向copy的Node，把原head Node指向原來head Node，並回傳新node 的next即可

```java
memory:  0x11  0x25  0x88   0xb5
                 ______________
                 |            |
                 |      ___   |
                 |      | |   |
                 r      r ↓   ↓
 head     ◇→→→   ◇→→→   ◇→→→  ◇→→→ null
          r             ↑     r  ↑
          |_____________|     |__|
                   
          
  next:    0x25  0x88   0xb5   null
  random:  0x88  0xb5   0x88   0xb5
  val:     1      1     2      2
  
  while run once:
  memory:  0x11   0x25   0x88    0xb5
                 ___________________
                 |                 |
                 |   ↑→→→→→→→→→→→↓  |
                 |   ↑   ___    ↓  |
                 |   ↑   | |    ↓  |  
                 r   ↑   r ↓    ↓  ↓ 
 head     ◇→→↓   ◇→→→↑   ◇→→→   ◇→→→  null
          r  ↓           ↑ ↑     r  ↑
          |  ↓→→→→→→→→→→→→↑ |     |  |
          |                |     |  |
          |________________|     |__|
                   
          
  next:    0x88   0xb5    0xb5   null
  random:  0x88   0xb5    0x88   0xb5
  val:     1      1       2       2
  
  while run two:
  memory:  0x11   0x25    0x88             0xb5
                 ______________________________
                 |                            |
                 |   ↑→→→→→→→→→→→→→→→→→→→→→→→↓  |
                 |   ↑   ____              ↓  | 
                 |   ↑   |  |              ↓  |  
                 r   ↑   r  ↓              ↓  ↓ 
 head     ◇→→↓   ◇→→→↑   ◇→→→null          ◇→→→  null
          r  ↓           ↑ ↑               r  ↑
          |  ↓→→→→→→→→→→→→↑ |               |  |
          |                |               |  |
          |________________|               |__|
                   
          
  next:    0x88   0xb5    null            null
  random:  0x88   0xb5    0x88            0xb5
  val:     1      1       2                2
```

因新的linked list 是Node dummyHead = new Node(); 所以回傳時，要回傳dummyHead.next才是

三部分是參考別人的方式程式碼如下:　我私自增加的print的部分來了解別人的程式碼。這個方式效率比我原來的好多！

```java
class Solution {
    public Node copyRandomList(Node head) {
        if(head == null){
            return head;
        }
         //print
        Node test = head;
        while(test != null){
            System.out.println("old.val = " +test.val + " , memory old " + test);
            
            if(test.next != null){
                System.out.println("old.next.val= " + test.next.val + " , memory old.next = " +test.next);
            }else{
                 System.out.println("old.next.val==null ");
            }
            
            if(test.random != null){
                System.out.println("old.random.val= " + test.random.val + " ,memory old.random = " + test.random );
                if(test.random.next != null){
                    System.out.println(", old.random.next.val= " +test.random.next.val+ " ,memory old.random.next = " + test.random.next );
                }
            }
            test= test.next;
            System.out.println("\n");
        }
        //print
        
        
        Node curr = head;
	Node next;
	// clone except for random pointers. Interweave alongside
	while (curr != null) {
		next = curr.next;
		Node copy = new Node(curr.val, null, null);
		curr.next = copy;
		copy.next = next;
		curr = next;
	}
        //print
 test = head;
        while(test != null){
            System.out.println("test.val = " +test.val + " , memory test " + test);
            
            if(test.next != null){
                System.out.println("test.next.val= " + test.next.val + " , memory test.next = " +test.next);
            }
            
            if(test.random != null){
                System.out.println("test.random.val= " + test.random.val + " ,memory test.random = " + test.random );
                 System.out.println(", test.random.next.val= " +test.random.next.val+ " ,memory test.random.next = " + test.random.next );
            }
            test= test.next;
            System.out.println("\n");
        }
        // print
	// link random
	curr = head;
	while (curr != null) {
		if (curr.random != null){
            
            System.out.println("curr.val = " +curr.val +", curr.random.val = " +curr.random.val);
            if(curr.next!= null ){
                System.out.println(" ,curr.next.val= " + curr.next.val);
                if(curr.next.random != null){
                    System.out.println(" ,curr.next.random.val= " + curr.next.random.val);
                }
            }
                if( curr.random.next != null){
                    System.out.println(" , curr.random.next.val = " +curr.random.next.val);
                }
			curr.next.random = curr.random.next;
        }
		curr = curr.next.next;
	}

        
         //print
 test = head;
        while(test != null){
            System.out.println("2 test.val = " +test.val + " , memory test " + test);
            
            if(test.next != null){
                System.out.println("2 test.next.val= " + test.next.val + " , memory test.next = " +test.next);
            }
            
            if(test.random != null){
                System.out.println("2 test.random.val= " + test.random.val + " ,memory test.random = " + test.random );
                if(test.random.next != null){
                     System.out.println("2 , test.random.next.val= " +test.random.next.val+ " ,memory test.random.next = " + test.random.next );
                }
            }
            test= test.next;
            System.out.println("\n");
        }
        // print
        
	// split list into original and clone
	curr = head;
	Node dummyHead = new Node();
	Node cloneTail = dummyHead; // always points to tail of clone
	Node cloneCurr;
	while (curr != null) {
		// save nodes before breaking links
		next = curr.next.next; // orig's next
		cloneCurr = curr.next; // clone's current

		// extract clone list
		cloneTail.next = cloneCurr;
		cloneTail = cloneCurr;

		// extract original
		curr.next = next;
		curr = next;
	}
	return dummyHead.next;
    }
}
```

看了別人的思路後，自已重寫一個一樣思路的。

程式碼:

```java
class Solution {
    public Node copyRandomList(Node head) {
        if(head == null){
            return head;
        }
        //print
        Node test = head;
        while(test != null){
            System.out.println("old.val = " +test.val + " , memory old " + test);
            
            if(test.next != null){
                System.out.println("old.next.val= " + test.next.val + " , memory old.next = " +test.next);
            }else{
                 System.out.println("old.next.val==null ");
            }
            
            if(test.random != null){
                System.out.println("old.random.val= " + test.random.val + " ,memory old.random = " + test.random );
                if(test.random.next != null){
                    System.out.println(", old.random.next.val= " +test.random.next.val+ " ,memory old.random.next = " + test.random.next );
                }
            }
            test= test.next;
            System.out.println("\n");
        }
        //print
        
        //original linked list ◇→◇→◇ ; new Linked list  ◇→■→◇→■→◇→■  ==>  new list ■→■→■
        
        Node n = head;
        Node t = null;
        while(n != null){
            t = n.next;
            Node copy = new Node(n.val , null, null);
            n.next = copy;
            copy.next = t;
            n= t;
        }
        
        n = head;
        
        while(n != null){
            if(n.random != null){
                n.next.random = n.random.next;
            }
            n = n.next.next;
        }

        Node r  = new Node();
        Node rTail = r;
        n = head;

        while(n != null){
            t = n.next.next;
            rTail.next = n.next;
            rTail = n.next;
            //Next pointer of node with val 1 from the original list was modified.
            //只有動到clone list是不行的，因為old 的list 的next 還是會指到新的list
            //現在 ◇→■→◇→■→◇→■  ==>  new list  ◇  ◇   ◇
            //                                    ↘   ↘   ↘
            //                                     ■→→→ ■→→ ■→→ null
            
            n.next = t;
             //現在 ◇→■→◇→■→◇→■  ==>  new list  ◇  ◇   ◇
            //                                      ↘   ↘   ↘
            //                                       ■→→→ ■→→ ■→→ null
            
                  //現在 ◇→■→◇→■→◇→■  ==>  new list  ◇→→ ◇   ◇
            //                                               ↘   ↘
            //                                            ■→→→ ■→→ ■→→ null
            
            //現在 ◇→■→◇→■→◇→■  ==>  head list  ◇→→ ◇→→  ◇→→ null
            //                                      
            //                          rr      □→→ ■→→→ ■→→ ■→→ null
            n =t;
        }
        
        //print
        Node rr = r;
        while(r != null){
            System.out.println("r.val = " + r.val+ " , memory r " + r);
            if(r.next != null){
                System.out.println("r.next.val= " + r.next.val + " , memory r.next = " +r.next);
            }else{
                 System.out.println("r.next.val==null ");
            }
            if(r.random != null){
                System.out.println("r.random.val= " + r.random.val + " ,memory r.random = " + r.random );
                if(r.random.next != null){
                    System.out.println(",r.random.next.val= " +r.random.next.val+ " ,memory r.random.next = " + r.random.next );
                }
            }
            System.out.println("\n");
            r = r.next;
        }
        //print
        return rr.next;
    }
}
```

去掉print版:

```java
class Solution {
    public Node copyRandomList(Node head) {
        if(head == null){
            return head;
        }
       
        
        //original linked list ◇→◇→◇ ; new Linked list  ◇→■→◇→■→◇→■  ==>  new list ■→■→■
        
        Node n = head;
        Node t = null;
        while(n != null){
            t = n.next;
            Node copy = new Node(n.val , null, null);
            n.next = copy;
            copy.next = t;
            n= t;
        }
        
        n = head;
        while(n != null){
            if(n.random != null){
                n.next.random = n.random.next;
            }
            n = n.next.next;
        }

        Node r  = new Node();
        Node rTail = r;
        n = head;
       // r = n.next;
      //  while(n != null){
      //      t = n.next;
      //      if(n.next != null){
      //         n.next = n.next.next;
      //      }else{
       //         n.next = null;
      //      }
      //      n =t;
      //  }
      // this get Next pointer of node with val 1 from the original list was modified. 
         while(n != null){
            t = n.next.next;
            rTail.next = n.next;
            rTail = n.next;
            n.next = t;
            n =t;
        }
        
        return rr.next;
    }
}
```

中間有注解的是產生「Next pointer of node with val 1 from the original list was modified.」因為Head的linked list的next Node指向新的linked list，這樣不行，所以要n.next = t; 才可以。
