【Check 43】2024-04-03 - 138. 随机链表的复制

思路

方法一：哈希表
- 哈希表记录【老节点-新节点】的映射关系
- 遍历原始链表，从map中获取每个节点的next和random信息进行赋值，最终从map中获取头节点对应的新节点返回
- O(n)/O(n)
方法二：拼接+拆分
- 先在原始链表中相邻复制，即node1->node1(new)->node2->node2(new)->node3->node3(new)
- 遍历相邻复制后的链表，给新节点设置random，复制节点都在原始节点的next，所以random也在原始节点random的next
- 例如node1节点对应的复制节点是node1(new)，node1(new).random = node1.random.next
- 双指针拆分原始节点和复制节点形成2条链表，返回复制节点链表
- O(n)/O(1)
  
  代码
```
// 哈希表
public Node copyRandomList(Node head) {
Map<Node, Node> map = new HashMap<>();
Node cur = head;
//收集 老节点-新节点 map
while (cur != null) {
    map.put(cur, new Node(cur.val));
    cur = cur.next;
}
Node oldCur = head;

while (oldCur != null) {
    Node newNode = map.get(oldCur);
    newNode.next = map.get(oldCur.next);
    newNode.random = map.get(oldCur.random);
    oldCur = oldCur.next;
}
return map.get(head);
}
```


```java
//拼接+拆分
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        while (cur != null) {
            //相邻复制
            Node temp = new Node(cur.val);
            temp.next = cur.next;
            cur.next = temp;
            cur = temp.next;
        }
        cur = head;
        while (cur != null) {
            //给复制节点设置random
            if (cur.random != null) {
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }
        cur = head.next;
        Node pre = head;
        Node res = head.next;
        while (cur.next != null) {
            pre.next = pre.next.next;
            cur.next = cur.next.next;
            pre = pre.next;
            cur = cur.next;
        }
        pre.next = null;

        return res;
    }

larscheng / algo

【Check 43】2024-04-03 - 138. 随机链表的复制 #144

思路

代码