[Leetcode LCR 154][Medium]-复杂链表的复制-链表
目录
一、题目描述
二、整体思路
三、代码
一、题目描述
原题地址
二、整体思路
这道题难点在于如何处理random。因为涉及到的所有节点都在同一链表，因此可以在链表上利用复制-拆分的方法去做。
先在链表上把每个节点复制自身一次，相当于cur与cur.next中间插入一个val与cur.val相同的新节点。
然后再复制random，从头遍历链表，cur.next是复制的新节点,cur.next.random=cur.random.next。遍历完的同时random也复制好了。注意不能cur.next.random=cur.random。因为这样的话就拆分不了链表了。
最后再拆分链表。
三、代码
/*
// 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 {
public Node copyRandomList(Node head) {
if(head==null){
return null;
}
Node cur=head;//复制节点(只复制next)
while(cur!=null){
Node nxt=cur.next;
cur.next=new Node(cur.val);
cur.next.next=nxt;
cur=nxt;
}
cur=head;
while(cur!=null){//复制random
cur.next.random=cur.random==null ? null : cur.random.next;
cur=cur.next.next;
}
cur=head;
Node res=cur.next;//拆分
Node temp=res;
while(cur!=null){
cur.next=cur.next==null ? null : cur.next.next;
temp.next=temp.next==null ? null :temp.next.next;
cur=cur.next;
temp=temp.next;
}
return res;
}
}