😀前言
在许多实际应用中，我们会遇到复杂链表的复制问题。复杂链表不同于一般的单链表，不仅每个节点有指向下一个节点的指针，还有一个特殊的指针 random，可以指向链表中的任意节点或 null。如何高效地复制这样一个复杂链表是一个常见的面试题。本文将详细解析这一问题，并提供一个Java实现。

复杂链表的复制

NowCoder

问题描述

给定一个复杂链表，其中每个节点包含一个整型值 label，一个指向下一个节点的指针 next，以及一个指向链表中任意节点的特殊指针 random。我们的任务是返回这个链表的深拷贝，即创建一个新的链表，其结构和原始链表完全相同，但各节点是独立的。

public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}

如上图所示，每个节点有两个指针，一个指向下一个节点，另一个随机指向链表中的任意节点或 null。

解题思路

为了高效地复制这个复杂链表，可以分为三个主要步骤：

1. 插入复制节点：在每个原节点的后面插入一个新的复制节点。新节点的 label 和原节点相同，next 指针指向原节点的下一个节点，而原节点的 next 指针则指向这个新插入的复制节点。

2. 建立 random 链接：在完成复制节点的插入后，遍历链表，为每个复制节点设置 random 指针，使其指向原节点 random 指针指向的节点的下一个节点。

3. 拆分链表：最后，将链表拆分为两个独立的链表，一个是原始链表，另一个是复制链表。我们要确保原链表和复制链表的结构和指针完全独立。

Java代码实现

以下是实现这个算法的Java代码，并附有详细的注释解释每一步的操作。

public class Solution {

    /**
     * 复制复杂链表
     * @param pHead 原链表的头节点
     * @return 复制链表的头节点
     */
    public RandomListNode Clone(RandomListNode pHead) {
        if (pHead == null) {
            return null;  // 如果原链表为空，直接返回null
        }

        // 第一步：在每个节点后面插入复制的节点
        RandomListNode cur = pHead;
        while (cur != null) {
            RandomListNode clone = new RandomListNode(cur.label);  // 创建新节点
            clone.next = cur.next;  // 复制节点的next指向原节点的下一个节点
            cur.next = clone;  // 原节点的next指向复制节点
            cur = clone.next;  // 移动到下一个原节点
        }

        // 第二步：为复制节点建立 random 链接
        cur = pHead;  // 重置指针到链表头
        while (cur != null) {
            RandomListNode clone = cur.next;  // 获取复制节点
            if (cur.random != null) {
                clone.random = cur.random.next;  // 复制节点的random指向原节点的random的下一个节点
            }
            cur = clone.next;  // 移动到下一个原节点
        }

        // 第三步：拆分链表，将复制节点从原链表中分离出来
        cur = pHead;  // 重置指针到链表头
        RandomListNode pCloneHead = pHead.next;  // 记录复制链表的头节点
        while (cur.next != null) {
            RandomListNode next = cur.next;  // 获取当前节点的下一个节点
            cur.next = next.next;  // 将当前节点的next指针指向下一个原节点
            cur = next;  // 移动到下一个节点
        }

        return pCloneHead;  // 返回复制链表的头节点
    }
}

代码解析

• 插入复制节点：
  • 首先，遍历原始链表，对于每个节点，创建一个新节点，将其插入到当前节点与下一个节点之间。
• 建立 random 链接：
  • 再次遍历链表，为每个复制节点设置 random 指针，指向原节点 random 所指向的节点的下一个节点。
• 拆分链表：
  • 最后一步，将原链表和复制链表分离。原链表恢复原样，而复制链表则成为一个独立的链表。

关键点解析

• 时间复杂度：
  • 整个过程只需遍历链表三次，时间复杂度为 O(N)，其中 N 是链表节点的数量。
• 空间复杂度：
  • 由于使用的是原地算法，没有额外的空间开销，空间复杂度为 O(1)。

😄总结

本文介绍了一种高效的算法来解决复杂链表的复制问题。通过在原链表中插入复制节点、建立 random 链接、以及最后的拆分操作，我们可以在O(N)的时间复杂度内完成链表的深拷贝。这种方法不仅简洁高效，而且避免了使用额外的数据结构，是面试中的经典题目之一。