力扣HOT100 - 138. 随机链表的复制

 

解题思路：

class Solution {public Node copyRandomList(Node head) {if(head==null) return null;Node p = head;//第一步，在每个原节点后面创建一个新节点//1->1'->2->2'->3->3'while(p!=null) {Node newNode = new Node(p.val);newNode.next = p.next;p.next = newNode;p = newNode.next;}p = head;//第二步，设置新节点的随机节点while(p!=null) {if(p.random!=null) {p.next.random = p.random.next;}p = p.next.next;}p = head;Node anotherNode = new Node(-1);//定义一个另外的新节点，给它赋值为-1Node cur = anotherNode;//第三步，将两个链表分离while(p!=null) {cur.next = p.next;cur = cur.next;p.next = cur.next;p = p.next;}return anotherNode.next;}
}	

注意:

Node p=head;与Node p=new Node(head.val);存在区别

前者的p为一个指向head对象的引用，换句话说，p和head 指向同一个对象，它们共享相同的引用，后者则创建一个全新的Node节点，p与head的val值相同。