1分钟，1道题，透彻掌握深复制、浅复制

double

发布于 2019-10-22 20:09:03

5370

Leetcode-138-deep copy of the list

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of the list. 给定一个链表，此链表有点特殊，里面有一个不大一样的属性节点，它指向链表中的另一个随机节点或不指向任何节点。要求返回这个链表的深拷贝。

先看一下定义的节点：

1  //Definition for singly-linked list with a random pointer.
2  public class RandomListNode {
3      public int label;
4      public RandomListNode next, random;
5      public RandomListNode(int x) { this.label = x; }
6  };

返回这个链表的深拷贝代码，大家可以先想想怎么做？

这里面有重要的几步，其中给next,random域重新申请一块heap比较好理解，问题在于，这就结束了吗？

大家请看，这就是深复制和浅复制的不同之处，如果是浅复制，到此结束，代码如下：

 1public class Solution {
 2
 3    public RandomListNode CopyRandomList(RandomListNode head) {
 4
 5        if(head==null) {
 6            return head;
 7        }
 8
 9        RandomListNode clonehead = new RandomListNode(head.label);
10
11        if(head.next!=null){
12            clonehead.next = new RandomListNode(head.next.label); 
13        }
14
15        if(head.random!=null) {
16            clonehead.random = new RandomListNode(head.random.label); 
17        } 
18        return clonehead;
19    }
20}

但是，深复制的话，必须要注意链表的节点是具备递归性质的，上面经过 clonehead.next = new RandomListNode(head.next.label)之后，仅仅是给label属性赋值了，而clonehead.next里面的属性next和random属性都是null，所以下面有一步很妙！

RandomListNode next = CopyRandomList(head.next); 就是这一步对吧？！妙哉！剩下的步骤就是将第一个节点链接到以next为头的链表中就OK了。

看懂了吗？

 1public class Solution {
 2
 3    public RandomListNode CopyRandomList(RandomListNode head) {
 4
 5        if(head==null) {
 6            return head;
 7        }
 8
 9        RandomListNode clonehead = new RandomListNode(head.label);
10
11        if(head.next!=null){
12            clonehead.next = new RandomListNode(head.next.label); 
13        }
14
15        if(head.random!=null) {
16            clonehead.random = new RandomListNode(head.random.label); 
17        }
18
19        //深复制体现在下面
20        RandomListNode next = CopyRandomList(head.next);
21        var cur = clonehead.next;
22        if(next!=null){
23            cur.next = next.next;
24            cur.random = next.random;
25        }    
26        return clonehead;
27    }
28}

通过这道题，如果你真正看明白了，相信你会更加深刻的理解：深复制，浅复制不管是在c,c++,java,python,… 任何语言都存对象深复制和浅复制问题。希望对你有用。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2018-10-05，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法