138. 复制带随机指针的链表

138. 复制带随机指针的链表

 

138. 复制带随机指针的链表

 

 

三步走方案

第一步:原链表基础上每个节点后新建一个完全一致的辅助节点,例如1->2->3,

调整后为1->1^->2->2^->3->3^

第二步:将辅助节点的random节点赋值为原节点random的next,比较绕口,这里举个例子

比如原节点1的random节点为3,此时1^的random也是3,但我们将3^赋值过去,使得辅助节点1^的

随机节点也为辅助节点

第三步:经过第二步的调整,所有辅助节点构成的链表即为所得,但此时原节点与辅助节点仍在同一链表上

因此我们需要将其拆分开。

时间O(n),空间O(n)(这里的n主要是开辟结果链表的空间,除此之外空间占用为O(1))

 1     public Node copyRandomList(Node head) {
 2         if(head==null){
 3             return head;
 4         }
 5 
 6         Node p = head;
 7         // 第一步:原链表基础上每个节点后新建一个完全一致的辅助节点
 8         while(p!=null){
 9             Node newNode = new Node(p.val);
10             newNode.next=p.next;
11             p.next = newNode;
12             p=newNode.next;
13         }
14         p=head;
15         // 第二步:将辅助节点的random节点赋值为原节点random的next(注意随机节点可能为空)
16         while(p!=null){
17             if(p.random!=null){
18                 p.next.random=p.random.next;
19             }
20             p=p.next.next;
21         }
22 
23         Node res = new Node(-1);
24         Node temp=res;
25         p=head;
26         // 第三步,拆分原链表
27         while(p!=null){
28             temp.next = p.next;
29             p.next = temp.next.next;
30             temp=temp.next;
31             p=p.next;
32         }
33         return res.next;
34     }

 

上一篇:LeetCode_138.复制带随机指针的链表


下一篇:「考试总结2021-04-07」进退