【算法】力扣：复制含有随机指针节点的链表

前置知识

• 数据结构-链表:解法二采用了存粹的链表知识和特殊处理，最优解。
• [可选]数据结构-哈希表：解法一使用了Java语言内置的哈希表
• 【兴趣】哈希思想， 设计哈希函数，开放寻址法，数组模拟哈希表。–笔者未写此法， 如果读者是哈希表的忠实信徒可以尝试写一下， 或无脑开一个大数组避免冲突能够过所有测试用例。

强调， 链表在算法设计其实是练习coding速度的， 笔试应该优先采取容器的方式加快速度， 面试必须采用最优解法。

题目:带随机指针的复制列表

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

解法1：Java内置HashMap

为了新链表与原链表建立一个直观的联系。
采用哈希表：

1. 遍历原链表，将原链表节点与新链表节点（创建一份副本）映射联系起来， 放入HashMap中。
2. 再次遍历原链表，根据key-value的对应关系，取出对应节点的副本，将next,random对应原链表节点的副本连接起来。

import java.util.HashMap;

//不要提交这个类
class Node {
	int val;
	Node next;
	Node random;

	public Node(int val) {
		this.val = val;
		this.next = null;
		this.random = null;
	}
}
//测试链接：https://leetcode.com/problems/copy-list-with-random-pointer/submissions/1426261747/
//提交：将类名改为Solution
public class CopyRandomList {
	public static Node copyRandomList(Node head) {
		if (head == null) {
			return null;//排除空表， 直接返回null
		}
		//初始化哈希表： key:原链表的节点 value:对应节点的副本
		HashMap<Node, Node> map = new HashMap<>();
		Node cur;
		//第一次遍历为每个节点拷贝一份副本， 存储到哈希表
		for (cur = head; cur != null; cur = cur.next) {
			map.put(cur, new Node(cur.val));// 拷贝原节点的一份副本。
		}
		//新链表的头节点和尾节点
		Node newHead = map.get(head);
		Node newTail = newHead;
		//第二次遍历原链表，连接指针。
		for (cur = head; cur != null; cur = cur.next) {
			//根据哈希表取出节点next,random的副本
			newTail.next = map.get(cur.next);
			newTail.random = map.get(cur.random);
			newTail = newTail.next;//尾节点往后跟。
		}
		return newHead;//返回头节点。
	}
}

时间复杂度:$O(n)$, 因为只遍历了两次原链表，哈希表插入查询是常量时间。
空间复杂度:$O(n)$, 因为存储了所有节点数及其副本。

解法2：技巧

接下来是进阶方法， 空间复杂度要做到$O(1)$。
前面的哈希表的作用？
存储原节点和副本的联系。通过哈希表， 原链表的连接方式可以很好映射到新链表的处理。
有没有同样的方法， 可以做到常数空间（不用哈希表）也能实现高效的寻址映射呢？
单链表有个很快的特性，已知节点可以迅速找到它的后继，因为只需要node.next即可。
基本思路：

1. 遍历原链表，并将每个节点生成的副本挂在该节点的后面，来达到快速查询的作用。
   比如原链表[1->2->3->null],这里以1'视作节点1的副本， 按照上述。应该拷贝原节点并修改原链表[1->1'->2->2'->3->3'->null]。
2. 上述可以快速寻址， 但是有什么显然的意义呢？答：修改random指针，比如1的random指针指向3这个节点，那么1’应该指向3’。那么再次遍历原链表修改random指针时。比如修改1‘的random指针，先通过1.random定位到3， 再通过3.next定位到3’， 再让1‘.random连接到3’。总结：第二次遍历根据副本是源节点的后继来设置副本的random指针。
3. 最后一步，由于我们修改了原链表，还要获得新链表。因此，需要实现链表分离。

public static Node copyRandomList(Node head) {
    // 单独处理空链表的情况，直接返回null
    if (head == null) {
        return null;
    }

    // 第一次遍历链表：为每个节点创建一个副本，并将副本插入到原节点的后面
    Node cur = head, next = null;
    while (cur != null) {
        next = cur.next; // 暂存原节点的下一个节点
        // 创建副本节点，并插入到原节点的后面
        cur.next = new Node(cur.val); 
        cur.next.next = next; // 将新创建的副本节点的next指向原节点的下一个节点
        cur = next; // 移动到原链表的下一个节点
    }

    // 第二次遍历链表：设置新节点的random指针
    cur = head;
    Node curCopy = null;
    while (cur != null) {
        next = cur.next.next; // 跳过副本节点，找到下一个原节点
        curCopy = cur.next; // cur的副本节点
        // 如果原节点的random指针不为空，设置副本节点的random指针指向原链表random节点的副本
        curCopy.random = cur.random == null ? null : cur.random.next;
        cur = next; // 移动到下一个原节点
    }

    // 第三次遍历链表：将原链表和副本链表分离
    cur = head;
    Node newHead = head.next; // 新链表的头节点
    while (cur != null) {
        next = cur.next.next; // 获取原链表的下一个节点（跳过副本节点）
        curCopy = cur.next; // 获取当前节点的副本
        // 恢复原链表的结构：将原节点的next指针指回到下一个原节点
        cur.next = next;
        // 连接副本链表的next指针：指向下一个副本节点
        curCopy.next = next == null ? null : next.next; // 处理next为null的情况
        cur = next; // 移动到下一个原节点
    }

    // 返回新链表的头节点
    return newHead;
}