剑指 Offer 35. 复杂链表的复制

题目链接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof

本文解法采取两种两种编程语言: 1.JavaScript (暴力解法)　　2.Java（暴力解法）

1.JavaScript

 1 /**
 2  * @param {Node} head
 3  * @return {Node}
 4  */
 5 var copyRandomList = function (head) {
 6   if (head == null) return head;
 7   let newHead = new Node(head.val, null, null);
 8   // 第一步，根据next复制链表以及其val、next；
 9   let tem1 = head.next;
10   let tem2 = newHead;
11   while (tem1 !== null) {
12     let tem3 = new Node(tem1.val, null, null);
13     tem2.next = tem3;
14     tem2 = tem2.next;
15     tem1 = tem1.next;
16   }
17   // 第二步，复制链表的random
18   let tem4 = newHead;
19   let tem5 = head;
20   // 遍历链表，复制每个结点的random
21   while (tem5 !== null) {
22     if (tem5.random === null) {
23       // 若当前结点的random
24       tem4.random = null;
25     } else {
26       let tem6 = head;
27       let tem7 = newHead;
28       // 将当前结点的random值与链表中的结点逐个比较
29       while (tem6 !== null) {
30         if (tem5.random === tem6) {
31           tem4.random = tem7;
32         }
33         tem6 = tem6.next;
34         tem7 = tem7.next;
35       }
36     }
37     tem4 = tem4.next;
38     tem5 = tem5.next;
39   }
40   return newHead;
41 };

2.Java

 1 class Node {
 2     int val;
 3     Node next;
 4     Node random;
 5 
 6     public Node(int val) {
 7         this.val = val;
 8         this.next = null;
 9         this.random = null;
10     }
11 }
12 
13 /**
14  * @author 不乏理想的三师弟
15  * 解法一
16  */
17 public Node copyRandomList(Node head) {
18     if(head == null) return null;
19     // 第一步：忽略random，复制一条链。
20     Node myHead = new Node(head.val);
21     Node tem = null;
22     Node tem2 = null;
23     if(head.next != null) {
24         tem = new Node(head.next.val);
25         myHead.next = tem;
26         tem2 = head.next.next;
27     }
28     while(tem2 != null) {
29         tem.next = new Node(tem2.val);
30         tem = tem.next;
31         tem2 = tem2.next;
32     }
33     /**
34      * 第二步：遍历链表，依次找出结点的random并复制
35      * 难点：确认random所指向结点的相对位置
36      * (题目要求：不只是要求值的相同，而且结点的相对位置也得相同)
37      * 手段：通过对比random所指结点的next是哪一个结点就知道其相对位置了
38      */
39     Node temMyHead = myHead;
40     Node temHead = head;
41     Node tem3;
42     
43     while(temHead != null) {
44         if(temHead.random == null) {
45             temMyHead.random = null;
46         }else {
47             // 保存当前结点random所指结点的next结点
48             tem = temHead.random.next; // tem变量的重复利用
49             // 再次遍历链表
50             tem2 = head;    // tem2变量的重复利用
51             tem3 = myHead;
52             while(tem2 != null) {
53                 if(tem2.next == tem) {
54                     temMyHead.random = tem3;
55                     break;
56                 }
57                 tem2 = tem2.next;
58                 tem3 = tem3.next;
59             }
60         }
61         temHead = temHead.next;
62         temMyHead = temMyHead.next;
63     }
64     return myHead;
65 }