题目描述

主要有两个考虑点：
- 不能改变原链表
- 新链表赋予 next、random 时，复制结点不一定存在

在这里插入图片描述

思路 && 代码

1. 哈希表法

O(n)、O(n)
参考了dalao的写法，这里哈希表用得非常巧妙～值得学习！
思路：在哈希表中建立 Node - CopyNode 的联系，在此基础上进行 next && random 的处理即可。

/*
// 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) {
        if(head == null) {
            return null;
        }
        
        // 哈希表做法<Node - CopyNode>
        Map<Node, Node> hashmap = new HashMap<>();
        for(Node temp = head; temp != null; temp = temp.next) {
            hashmap.put(temp, new Node(temp.val));
        }
        for(Node temp = head; temp != null; temp = temp.next) {
            // next 的处理
            hashmap.get(temp).next = hashmap.get(temp.next);
            // random 的处理
            hashmap.get(temp).random = hashmap.get(temp.random);
        }
        return hashmap.get(head);
    }
}

2. 原地算法

O(n)、O(1)，相对于方法1，此处不需要占用额外空间～
注意：原链表的恢复、边界结点的处理

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) {
            return null;
        }
        
        // 原地算法
        // 1. 首先 1 -> 2 -> 3 变成 1 -> 1* -> 2 -> 2* -> 3 -> 3*
        for(Node temp = head; temp != null; temp = temp.next.next) {
            Node copy = new Node(temp.val);
            copy.next = temp.next;
            temp.next = copy;
        }
        // 2. 进行 random 的处理
        for(Node temp = head; temp != null; temp = temp.next.next) {
            if(temp.random != null) {
                temp.next.random = temp.random.next;
            }
        }

        // 3. 分开 1 -> 1* -> 2 -> 2* -> 3 -> 3* 变成 1* -> 2* -> 3*
        Node copyHead = head.next;
        for(Node temp = head; temp != null; temp = temp.next) {
            // 取到原本的正确next
            Node nextNode = temp.next.next;
            // * -> *
            if(nextNode != null) {
                temp.next.next = temp.next.next.next;
            }
            // 1 -> 2
            temp.next = nextNode;
        }
        return copyHead;
    }
}