LeetCode——复制带随机指针的链表

NO.138 复制带随机指针的链表中等

思路一：HashMap 第一遍复制节点的 val ，next 和 random 暂时为空，并将源节点和克隆节点形成映射存放在一个 HashMap 中。

public Node copyRandomList(Node head) {
    if (head == null) return null;
    HashMap<Node, Node> map = new HashMap<>();
    Node p = head;
    while (p != null) {
        map.put(p, new Node(p.val));
        p = p.next;
    }
    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);
}

时间复杂度：O(n)

空间复杂度：O(n)

思路二：常数空间 不借助 HashMap 也可以完成克隆，思路看图：

输入如下图 [[1,2],[2,3],[3,null],[4,null]]
复制源节点。
生成克隆节点的 random 指针。
将原链表和克隆链表分离。

实现的时候，谨记：源节点的 next 就是其的克隆节点。代码对照着图片很简单的。

public Node copyRandomList(Node head) {
    if (head == null) return null;
    //克隆源节点
    Node p = head;
    while (p != null) {
        Node temp = p.next;
        p.next = new Node(p.val);
        p.next.next = temp;
        p = temp;
    }
    //给克隆节点的 random 赋值
    p = head;
    while (p != null) {
        if (p.random != null) p.next.random = p.random.next;
        p = p.next.next;
    }
    //拆分
    p= head;
    Node cloneHead = p.next;
    Node cloneP = cloneHead;
    while (cloneP.next != null) {
        //原链表
        p.next = p.next.next;
        p=p.next;
        //克隆链表
        cloneP.next = cloneP.next.next;
        cloneP = cloneP.next;
    }
    //最后不要忘了给原链表收尾
    p.next = null;
    return cloneHead;
}

时间复杂度：O(n)

空间复杂度：O(1)

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github

NO.138 复制带随机指针的链表 中等

NO.138 复制带随机指针的链表中等