模拟 + 哈希表

如果不考虑 random 指针的话，对一条链表进行拷贝，我们只需要使用两个指针：一个用于遍历原链表，一个用于构造新链表（始终指向新链表的尾部）即可。这一步操作可看做是「创建节点 + 构建 next 指针关系」。

现在在此基础上增加一个 random 指针，我们可以将 next 指针和 random 指针关系的构建拆开进行：

  1. 先不考虑 random 指针，和原本的链表复制一样，创建新新节点，并构造 next 指针关系，同时使用「哈希表」记录原节点和新节点的映射关系；
  2. 对原链表和新链表进行同时遍历，对于原链表的每个节点上的 random 都通过「哈希表」找到对应的新 random 节点，并在新链表上构造 random 关系。

代码：

import java.util.*;
public class Solution {
    public RandomListNode Clone(RandomListNode head) {
        Map<RandomListNode, RandomListNode> map = new HashMap<>();
        RandomListNode dummy = new RandomListNode(-1);
        RandomListNode tail = dummy, tmp = head;
        while (tmp != null) {
            RandomListNode node = new RandomListNode(tmp.label);
            map.put(tmp, node);
            tail.next = node;
            tail = tail.next;
            tmp = tmp.next;
        }
        tail = dummy.next;
        while (head != null) {
            if (head.random != null) tail.random = map.get(head.random);
            tail = tail.next;
            head = head.next;
        }
        return dummy.next;
    }
}
  • 时间复杂度：
  • 空间复杂度：

模拟（原地算法）

显然时间复杂度上无法优化，考虑如何降低空间（不使用「哈希表」）。

我们使用「哈希表」的目的为了实现原节点和新节点的映射关系，更进一步的是为了快速找到某个节点 random 在新链表的位置。

那么我们可以利用原链表的 next 做一个临时中转，从而实现映射。

具体的，我们可以按照如下流程进行：

  1. 对原链表的每个节点节点进行复制，并追加到原节点的后面；
  2. 完成 操作之后，链表的奇数位置代表了原链表节点，链表的偶数位置代表了新链表节点，且每个原节点的 next 指针执行了对应的新节点。这时候，我们需要构造新链表的 random 指针关系，可以利用 link[i + 1].random = link[i].random.next， 为奇数下标，含义为 新链表节点的 random 指针指向旧链表对应节点的 random 指针的下一个值；
  3. 对链表进行拆分操作。

image.png

代码：

import java.util.*;
public class Solution {
    public RandomListNode Clone(RandomListNode head) {
        if (head == null) return null;
        RandomListNode dummy = new RandomListNode(-1);
        dummy.next = head;
        while (head != null) {
            RandomListNode node = new RandomListNode(head.label);
            node.next = head.next;
            head.next = node;
            head = node.next;
        }
        head = dummy.next;
        while (head != null) {
            if (head.random != null) {
                head.next.random = head.random.next;
            }
            head = head.next.next;
        }
        head = dummy.next;
        RandomListNode ans = head.next;
        while (head != null) {
            RandomListNode tmp = head.next;
            if (head.next != null) head.next = head.next.next;
            head = tmp;
        }
        return ans;
    }
}
  • 时间复杂度：
  • 空间复杂度：

最后

这是我们「剑指 の 精选」系列文章的第 No.25 篇，系列开始于 2021/07/01。

该系列会将牛客网「剑指 Offer」中比较经典而又不过时的题目都讲一遍。

在提供追求「证明」&「思路」的同时，提供最为简洁的代码。

欢迎关注，交个朋友 (｀・ω・´)