链接

https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/
难度： #中等

题目

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

示例 3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

示例 4：

输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。

提示：

• -10000 <= Node.val <= 10000
• Node.random 为空（null）或指向链表中的节点。
• 节点数目不超过 1000 。

代码框架

/*
// 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) {
 }
}

题目解析

解答思路1：
使用递归方式遍历链表，
从后往前复制链表，
在递归遍历下一个结点之前，
首先复制当前结点到新结点，
然后把旧结点映射的新结点，
然后遍历下一个结点，
直到最后一个结点，
这时Map中有全部旧结点到新结点的映射关系，
然后从最后一个结点开始处理random值，
首先找到random指向的旧结点，
根据旧结点找到新的结点即可。

解答思路2：
使用2个for循环，
第1个for循环复制链表的所有节点，
同时保存旧结点对应的新结点，
第2个for循环处理next和random值，
根据next和random指向的旧结点，
分别找到其对应的新的结点即可。
该思路的优点是容易理解，
并且代码实现很简单。

解答思路3：
原地修改的方法：
复制一个新的节点在原有节点之后，
如1 -> 2 -> 3 -> null 复制完
是1 -> 1 -> 2 -> 2 -> 3 - > 3 -> null，
从头开始遍历链表，
通过 cur.next.random = cur.random.next 可以将复制节点的Random串起来，
注意判断 cur.random 是否存在
最后将复制完的链表一分为二。
该思路相比思路1并未有本质上的优化提升，
同时又很大的操作链表的复杂度，
但是可以扩展链表的使用思路，
且锻炼对链表的操作能力。

测试用例

package edu.yuwen.sowrd.num35.solution;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import edu.yuwen.sowrd.num35.Node;
import edu.yuwen.sowrd.num35.sol3.Solution;

public class SolutionTest {
    /**
     * 示例1：
     * 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
     *  输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
     */
    @Test
    public void testCase1() {
        Solution solution = new Solution();

        Node head = getNodeHead();
        Node newHead = solution.copyRandomList(head);

        // 返回的新链表不能和旧链表相同
        Assertions.assertNotEquals(head, newHead);

        for (Node old = head, newN = newHead; old != null; old = old.next, newN = newN.next) {
            // 检查是否是深拷贝
            Assertions.assertNotEquals(old, newN);
            Assertions.assertEquals(old.val, newN.val);
        }

        for (Node node = head; node != null; node = node.next) {
            System.out.println(node.val + " ,next->" + getNextValue(node)
                    + " ,random->" + getRandomValue(node));
        }
        System.out.println("-----------------------------------");
        for (Node node = newHead; node != null; node = node.next) {
            System.out.println(node.val + " ,next->" + getNextValue(node)
                    + " ,random->" + getRandomValue(node));
        }
    }

    public Node getNodeHead() {
        Node node0 = new Node(7);
        Node node1 = new Node(13);
        Node node2 = new Node(11);
        Node node3 = new Node(10);
        Node node4 = new Node(1);

        node0.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = null;

        node0.random = null;
        node1.random = node0;
        node2.random = node4;
        node3.random = node2;
        node4.random = node0;

        Node head = node0;
        return head;
    }

    public Integer getRandomValue(Node node) {
        return node.random == null ? null : node.random.val;
    }

    public Integer getNextValue(Node node) {
        return node.next == null ? null : node.next.val;
    }

    /**
     * 输入：head = []
     * 输出：[]
     * 解释：给定的链表为空（空指针），因此返回 null。
     */
    @Test
    public void testCase2() {
        Solution solution = new Solution();

        Node head = null;
        Node newHead = solution.copyRandomList(head);

        // 返回的新链表不能和旧链表相同
        Assertions.assertEquals(null, newHead);
    }
}

解答1 推荐

package edu.yuwen.sowrd.num35.sol1;

import java.util.HashMap;
import java.util.Map;

import edu.yuwen.sowrd.num35.Node;

/**
 *解答思路1：
 *使用递归方式遍历链表，  
 *从后往前复制链表，
 *在递归遍历下一个结点之前，
 *首先复制当前结点到新结点，  
 *然后把旧结点映射的新结点，  
 *然后遍历下一个结点，  
 *直到最后一个结点，
 *这时Map中有全部旧结点到新结点的映射关系，
 *然后从最后一个结点开始处理random值，  
 *首先找到random指向的旧结点，  
 *根据旧结点找到新的结点即可。 
 */
public class Solution {
    // 映射旧的结点对应的新的结点
    Map<Node, Node> old2New = new HashMap<>();

    public Node copyRandomList(Node head) {
        // 头结点为空，或者处理到尾结点了
        if (head == null) {
            return null;
        }
        Node newNode = new Node(head.val);
        old2New.put(head, newNode);

        // 递归处理下一个结点，并且获得下一个结点
        Node nextNode = copyRandomList(head.next);
        // 当前结点指向下一个结点
        newNode.next = nextNode;
        // HashMap的get()入参为null，会返回null
        Node newRandomNode = old2New.get(head.random);
        newNode.random = newRandomNode;

        return newNode;
    }
}

解答2

package edu.yuwen.sowrd.num35.sol2;

import java.util.HashMap;
import java.util.Map;

import edu.yuwen.sowrd.num35.Node;

/**
 * 解答思路2：
 * 使用2个for循环，  
 * 第1个for循环复制链表的所有节点，  
 * 同时保存旧结点对应的新结点，  
 * 第2个for循环处理next和random值，
 * 根据next和random指向的旧结点，  
 * 分别找到其对应的新的结点即可。 
 */
public class Solution {

    // 记录旧的结点对应的新的结点
    Map<Node, Node> old2New = new HashMap<>();

    public Node copyRandomList(Node head) {
        // 头结点为空，或者处理到尾结点了
        if (head == null) {
            return null;
        }

        // 创建新结点，并且映射旧结点到新结点的
        for (Node cur = head; cur != null; cur = cur.next) {
            Node newNode = new Node(cur.val);
            old2New.put(cur, newNode);
        }

        // 根据映射表，更新新链表的每个结点
        Node newCur = old2New.get(head);
        for (Node cur = head; cur != null; cur = cur.next) {
            newCur.next = old2New.get(cur.next);
            newCur.random = old2New.get(cur.random);
            // 新链表移动到下一个结点
            newCur = newCur.next;
        }

        // 返回新链表的头结点
        return old2New.get(head);
    }
}

解答3

package edu.yuwen.sowrd.num35.sol3;

import edu.yuwen.sowrd.num35.Node;

/**
 * 解答思路3：
 * 原地修改的方法：
 * 复制一个新的节点在原有节点之后，
 * 如1 -> 2 -> 3 -> null 复制完
 * 是1 -> 1 -> 2 -> 2 -> 3 - > 3 -> null，
 * 从头开始遍历链表，
 * 通过 cur.next.random = cur.random.next 可以将复制节点的Random串起来，
 * 注意判断 cur.random 是否存在
 * 最后将复制完的链表一分为二。
 *
 */
public class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }

        // 由于插入了复制过的结点，要跳过下一个结点
        for (Node cur = head; cur != null; cur = cur.next.next) {
            // 在当前结点插入复制的结点
            Node newN = new Node(cur.val);
            newN.next = cur.next;
            cur.next = newN;
        }

        // 根据原节点的Random初始化复制节点的Random
        for (Node cur = head; cur != null; cur = cur.next.next) {
            Node newN = cur.next;
            if (cur.random != null) {
                // 不直接使用当前节点的random,而是指向下一个复制的结点
                newN.random = cur.random.next;
            }
        }

        // 保存复制链表的头结点
        Node newHead = head.next;
        // 将复制的链表拆分出来
        for (Node cur = head; cur != null; cur = cur.next) {
            Node newN = cur.next;
            // 当前结点指向原始链表的下一个结点
            cur.next = newN.next;
            if (newN.next != null) {
                // 复制链表的结点指向下一个结点的复制节点
                newN.next = newN.next.next;
            }
        }
        return newHead;
    }
}