【Leetcode Top 100】138. 随机链表的复制

问题背景

给你一个长度为 $n$ 的链表，每个节点包含一个额外增加的随机指针 $random$，该指针可以指向链表中的任何节点或空节。
构造这个链表的 深拷贝。 深拷贝应该正好由 $n$ 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 $next$ 指针和 $random$ 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 $X$ 和 $Y$ 两个节点，其中 $X.random=Y$。那么在复制链表中对应的两个节点 $x$ 和 $y$，同样有 $x.random=y$。
返回复制链表的头节点。

数据约束

• $0\le n\le 1000$
• $-10^4\le Node.val\le 10^4$
• $Node.random$ 为 $null$ 或指向链表中的节点。

解题过程

经典链表操作题，解决的关键在于能否想到把新建的复制节点添加到原节点的后一个。
通过上述方案复制完整个链表之后，只要能够分离链表即可，参考 奇偶链表，本题中由于原链表的后一个节点是它本身的复制，一定存在，分离的时候可以少一个判断。

注意数据范围，头节点可能为空，要单独处理。

具体实现

/*
// 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) {next = cur.next;cur.next = new Node(cur.val, cur.next); // 题中没说明这个构造器，实际上是存在的cur.next.next = next;cur = cur.next.next;}// 重置工作指针cur = head;// 给每个新节点的随机域赋值while(cur != null) {if(cur.random != null) {cur.next.random = cur.random.next;}cur = cur.next.next;}// 分离原链表和复制之后的链表Node copyHead = head.next, copy;cur = head;while(cur.next.next != null) {copy = cur.next; // 记录下一个节点cur.next = cur.next.next; // 调整原链表的 next 指针copy.next = copy.next.next; // 调整新链表的 next 指针cur = cur.next; // 后移工作指针}// 原链表的最后一个节点要指空cur.next = null;return copyHead;}
}