必会算法：深度克隆带随机节点的链表

你好戴先生

发布于 2022-03-30 20:46:26

5270

发布于 2022-03-30 20:46:26

文章被收录于专栏：戴言泛滥

题目

大家好，我是戴先生

今天讲解一下深度克隆带随机节点链表的两种解法

节点的定义如下

public class NodeWithRandomNext {
    public Integer value;
    public NodeWithRandomNext next;
    public NodeWithRandomNext random;

    public NodeWithRandomNext() {
    }

    public NodeWithRandomNext(Integer value) {
        this.value = value;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o == null || getClass() != o.getClass()) {
            return false;
        }
        NodeWithRandomNext that = (NodeWithRandomNext) o;
        return Objects.equals(value, that.value);
    }

    @Override
    public int hashCode() {
        return Objects.hash(value);
    }


    @Override
    public String toString() {
        NodeWithRandomNext temp = this;
        StringBuilder str = new StringBuilder();
        while (temp != null) {

            str.append("(")
                    .append(temp.value)
                    .append(",")
                    .append(Objects.isNull(temp.random) ? "null" : temp.random.value)
                    .append(")")
                    .append("->");
            temp = temp.next;
        }
        str.append("null");
        return str.toString();
    }
}

什么是带随机节点的链表呢？

在正常链表的基础上

每一个节点除了next指针指向下一个节点

还有一个random指针

随机指向链表中的任意节点或者null

那么如何深度克隆这样一个链表呢？

题解

克隆的意思就是在原链表的基础上复制出一条一模一样（节点值相等）的链表

首先我们需要明确两个概念：深克隆与浅克隆

深克隆要求复制后的链表的每一个节点都是新创建的

与原链表相比不能占用同一块内存区域

浅克隆可以简单理解为复制出一个指向原链表的指针

复制后的链表和原链表占用同一块内存区域

这个题目的考点在于如何处理随机指针

需要同时兼顾创建新链表节点和梳理指针指向的问题

所以妄图通过一次遍历就昨晚这两件事是不太可能了

理解了题目之后，我们很容易想到思路1

思路

首先通过next指针遍历并复制一遍链表

复制前后的节点通过map存储对应关系

然后再次通过next指针遍历链表拼接新链表

因为每一个链表节点都已经复制完成了

所以也可以同时将每一个random指针的指向关系也梳理好

首先我们复制每一个节点

并使用map存储

然后遍历原链表第一个节点

并从map中取出第一个节点的复制节点

接着根据原始节点梳理第一个节点next节点

然后就是第一个节点的random指针指向了

根据原链表可知指向节点5

此时便可以从map中取出节点5的复制节点

并将复制节点1的random指向复制节点5

同理可接着处理接下来的所有节点

直到原链表遍历结束

至此链表的深克隆就完成了

代码实现1

思路1的代码实现如下

    public static NodeWithRandomNext deepClone1(NodeWithRandomNext list) {
        if (list == null) {
            return null;
        }

        NodeWithRandomNext pointer = new NodeWithRandomNext();
        NodeWithRandomNext temp = list;
        Map<NodeWithRandomNext, NodeWithRandomNext> nodeMap = new HashMap<>();
        // 先遍历所有节点，并复制一份
        while (temp != null) {
            nodeMap.putIfAbsent(temp, new NodeWithRandomNext(temp.value));
            temp = temp.next;
        }
        temp = nodeMap.get(list);
        pointer.next = temp;
        // 再次遍历所有节点，并梳理前后和随机关系
        while (temp != null) {
            temp.next = nodeMap.get(list.next);
            temp.random = nodeMap.get(list.random);
            list = list.next;
            temp = temp.next;
        }

        return pointer.next;
    }

思路2

但是思路1的方法有一个缺点

就是需要额外的存储空间来存储原节点和复制节点的对应关系

那么有没有什么办法可以节省这部分空间呢？

要解决这个问题其实就是换一种方式存储已经复制好的所有节点

同时还要记录下原节点和复制节点之间的对应关系

有一种很巧妙的思路就是将复制后的节点拼接到节点上

以此解决复制节点的存储问题

那么怎么解决原节点和复制节点之间的对应关系呢？

我们让每一个复制节点紧跟原节点不就可以了吗

首先第一步就是通过原链表的next指针遍历链表

同时首先复制第一个节点

然后将原节点1的next指针指向复制节点1

同时将复制节点1的next指针指向原节点2

这样我们就将复制节点1挂接到原链表中了

同样的方法我们处理节点2

以及剩余的所有节点

至此第一遍遍历完成

接下来我们处理随机节点

因为经过第一遍的遍历处理

每一个复制节点都是紧跟原节点的

所以每一个复制节点的random节点

也是紧跟原节点的random节点的next节点的

所以第一遍遍历我们就可以解决复制节点的random指针的指向问题了

至此第二遍遍历完成

所有复制节点的随机节点指向问题也都梳理完成

接着我们只需要借助一个temp临时指针

将复制节点剥离出来就行了

拿第一个节点举例

首先我们断开原节点1的next指针

并让它指向原节点2

然后断开复制节点1的next指针

并将复制节点1的next指针指向复制节点2

至此复制节点1就成功剥离出来了

同理我们可以处理剩下的所有节点

第三遍遍历完成之后

复制后的链表就完全剥离出来了

至此带随机指针链表的深克隆完成

并且时间复杂度为O(N)

没有使用额外的空间，所以空间复杂度为O(1)

代码实现2

思路2的代码实现如下

    public static NodeWithRandomNext deepClone2(NodeWithRandomNext list) {
        if (list == null) {
            return null;
        }
        // 复制所有节点
        copy(list);
        // 挂接所有随机节点
        copyRandom(list);
        // 拆分出复制后的节点，并返回
        return split(list);
    }

    private static void copy(NodeWithRandomNext list) {
        NodeWithRandomNext node = list;
        while (node != null) {
            NodeWithRandomNext copy = new NodeWithRandomNext(node.value);
            copy.next = node.next;
            node.next = copy;
            node = copy.next;
        }
    }

    private static void copyRandom(NodeWithRandomNext list) {
        NodeWithRandomNext node = list;
        while (node != null && node.next != null) {
            if (node.random != null) {
                node.next.random = node.random.next;
            }
            node = node.next.next;
        }
    }

    private static NodeWithRandomNext split(NodeWithRandomNext list) {
        NodeWithRandomNext result = list.next;
        NodeWithRandomNext temp = list.next;
        while (list != null && list.next != null) {
            list.next = list.next.next;
            list = list.next;
            if (temp != null && temp.next != null) {
                temp.next = temp.next.next;
                temp = temp.next;
            }
        }
        return result;
    }

测试验证

写一个测试方法测试一下

    public static void main(String[] args) {
        NodeWithRandomNext list = new NodeWithRandomNext(1);
        NodeWithRandomNext temp = list;
        NodeWithRandomNext cross = null;
        for (int i = 2; i < 10; i++) {
            temp.next = new NodeWithRandomNext(i);
            temp = temp.next;
            if (i == 5) {
                cross = temp;
                cross.random = cross;
            }
            if (i == 8) {
                temp.random = cross;
            }
        }

        NodeWithRandomNext clone1 = deepClone1(list);
        NodeWithRandomNext clone2 = deepClone2(list);
        System.out.printf("深克隆带随机指针的链表1%s：%s\n", list == clone1 ? "失败" : "成功", clone1);
        System.out.printf("深克隆带随机指针的链表2%s：%s\n", list == clone2 ? "失败" : "成功", clone2);
    }

运行成功！