LeetCode 138. 随机链表的复制

138. 随机链表的复制

解题思路

1. 遍历原链表，在每个原节点后面插入它的复制节点
2. 赋值 random，原节点的 random 指向的节点后面正好是它的复制节点
3. 把交错的两条链表拆开，得到完整的复制链表

   不用哈希表
   解题思路

参考代码

class Solution {
    public Node copyRandomList(Node head) {
        // 复制原链表的每个节点
        for(Node cur = head; cur != null; cur = cur.next.next) {
            cur.next = new Node(cur.val, cur.next);
        }
        // 遍历交错链表中的原链表节点
        for(Node cur = head; cur != null; cur = cur.next.next) {
            // 复制 random
            if(cur.random != null) {
                cur.next.random = cur.random.next;
            }
        }

        Node dummy = new Node(0);
        Node tail = dummy;
        for(Node cur = head; cur != null; cur = cur.next, tail = tail.next) {
            Node copy = cur.next;
            tail.next = copy;
            cur.next = copy.next;
        }
        return dummy.next;
    }
}