leetcode--138. 复制带随机指针的链表

138. 复制带随机指针的链表 面试题35. 复杂链表的复制

1、HashMap

• 第一遍复制节点的 val ，next 和 random 暂时为空，并将源节点和克隆节点形成映射存放在一个 HashMap 中。
• 第二遍拷贝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;

        // 遍历源结点， 将节点存储到hashmap中，对应拷贝的节点
        HashMap map = new HashMap();
        Node p = head;
        while(p != null) {
            map.put(p, new Node(p.val));
            p = p.next;
        }

        // 第二次遍历，拷贝next,random节点
        p = head;
        while(p != null) {
            map.get(p).next = map.get(p.next);
            map.get(p).random = map.get(p.random);
            p = p.next;
        }
        return map.get(head);

        
    }
}

2、 空间迭代

  与上面提到的维护一个旧节点和新节点对应的字典不同，我们通过扭曲原来的链表，并将每个拷贝节点都放在原来对应节点的旁边。这种旧节点和新节点交错的方法让我们可以在不需要额外空间的情况下解决这个问题。让我们看看这个算法如何工作

1、遍历原来的链表并拷贝每一个节点，将拷贝节点放在原来节点的旁边，创造出一个旧节点和新节点交错的链表。 2、迭代这个新旧节点交错的链表，并用旧节点的 random 指针去更新对应新节点的 random 指针。

3、现在 random 指针已经被赋值给正确的节点， next 指针也需要被正确赋值，以便将新的节点正确链接同时将旧节点重新正确链接。

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;

        Node p = head;
        while(p != null) {
            // 拷贝节点
            Node copyNode = new Node(p.val);
            // 插入原节点后面
            copyNode.next = p.next;
            p.next = copyNode;

            p = copyNode.next;
        }

        // 拷贝random节点
        p = head;
        while(p != null) {
            p.next.random = p.random == null ? null: p.random.next; 
            p = p.next.next;
        }

        // 注意此处不修改原链表
        Node oldN = head;
        Node newN = head.next;
        Node newhead = newN;
        while(oldN != null) {
            oldN.next = oldN.next.next;
            newN.next = newN.next == null ? null: newN.next.next;
            oldN = oldN.next;
            newN = newN.next;
        }
        return newhead;
    }
}