复杂链表的复制

复杂链表的复制

题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针：一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的 head。

注意：输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空。

解题思路

初次审题看似简单，实质是复制链表，但在实际操作中容易出现各种 Bug，例如提交后提示返回空指针。这通常是因为未严格遵守“不返回参数中的节点引用”这一要求，即需要重新创建一个链表，并将原链表节点逐个复制过来。

目前主要有两种实现思路：

1. 递归法
   每一次递归复制一个节点。该思路简洁且代码量少。使用 JavaScript 实现该思路可通过评测，但 Java 实现可能因评测系统差异或栈深度限制遇到问题。

2. 迭代法（交错复制）
   另一种思路是通过三次遍历完成复制，具体步骤如下（图解参考自网络）：

   1. 复制节点：将每一个复制的节点放在原节点后面。
      
   2. 复制随机节点：利用交错关系设置随机指针。
      
   3. 拆分链表：将复制的链表和原来的链表分开。
      

   在代码实现过程中，逻辑细节较难把握，但结合上述图解会更易理解。

代码实现

JavaScript 版本（递归思路）

/*function RandomListNode(x){
    this.label = x;
    this.next = null;
    this.random = null;
}*/
function Clone(pHead) {
    if (pHead == null)
        return pHead;
    var a = new RandomListNode(pHead.label);
    a.random = pHead.random;
    a.next = Clone(pHead.next);
    return a;

    // write code here
}

Java 版本（迭代思路）

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

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

public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        if (pHead == null)
            return null;

        // 1. 复制节点并插入原节点之后
        RandomListNode p1 = pHead;
        while (p1 != null) {
            RandomListNode temp = new RandomListNode(p1.label);
            temp.next = p1.next;
            p1.next = temp;
            p1 = temp.next;
        }

        // 2. 复制随机指针
        p1 = pHead;
        while (p1 != null) {
            if (p1.random != null)
                p1.next.random = p1.random.next; // 易错点，需结合分析图理解
            p1 = p1.next.next;
        }

        // 3. 拆分链表
        RandomListNode head = pHead.next;
        RandomListNode temp1 = head;
        p1 = pHead;
        while (p1.next != null) {
            temp1 = p1.next;
            p1.next = temp1.next;
            p1 = temp1;
        }
        return head;
        //  return pHead;
    }
}

说明：本文题目及图解源自牛客网《剑指 Offer》经典面试题（2016 年存档）。不同在线评测系统（OJ）对递归深度或内存限制可能存在差异，实际应用中建议根据具体环境选择迭代或递归方案。