「复制带随机指针的链表」的一个很巧妙解法

题目来源于 LeetCode 上第 138 号问题:复制带随机指针的链表。题目难度为 Medium,目前通过率为 40.5% 。

题目描述

给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的深拷贝

示例:

输入:
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}

解释:
节点 1 的值是 1,它的下一个指针和随机指针都指向节点 2 。
节点 2 的值是 2,它的下一个指针指向 null,随机指针指向它自己。

题目解析

  1. 在原链表的每个节点后面拷贝出一个新的节点

  2. 依次给新的节点的随机指针赋值,而且这个赋值非常容易 cur->next->random = cur->random->next

  3. 断开链表可得到深度拷贝后的新链表

之所以说这个方法比较巧妙是因为相较于一般的解法(如使用 Hash map )来处理,上面这个解法 不需要占用额外的空间

动画描述

动画描述

动画描述

top Created with Sketch.