题目描述
截图来自官方
代码
/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/
class Solution {
// 没做出来，看官方解法3,抽时间把别的解法看看
public Node copyRandomList(Node head) {
if(head==null){
return null;
}
Node temp=head;
// 先将每个节点复制一个跟在原来的每个节点后面
while(temp!=null){
Node newNode=new Node(temp.val);
newNode.next=temp.next;
temp.next=newNode;
temp=newNode.next;
}
//参考原节点的random指向，将每个新节点的random指向正确位置
temp=head;
while(temp!=null){
// if(temp.random!=null){
// temp.next.random=temp.random.next;
// }else{
// temp.next.random=null;
// }
// 用三元表达式替换
temp.next.random=(temp.random!=null)?temp.random.next:null;
temp=temp.next.next;
}
// 断链表，将新节点依次和旧节点断开并连接成一条新链表
Node newHead=head.next;
Node oldHead=head;
temp=newHead;
while(temp!=null){
// // 看题目要求不要求保存原链表的结构了,不保存会报错。如果不要求保存这样写就行了，原来的就不用管了。
// if(temp.next!=null){
// temp.next=temp.next.next;
// temp=temp.next;
// }else{
// break;
// }
// 要求恢复原来的链表。则生成新链表的同时恢复旧的
if(temp.next!=null){
oldHead.next=temp.next;
temp.next=temp.next.next;
temp=temp.next;
oldHead=oldHead.next;
}else{
// 将原链表的最后一个节点的next手动置为null
oldHead.next=null;
break;
}
}
return newHead;
}
}
