剑指 Offer 35. 复杂链表的复制 (opens new window)

注意，构建复杂链表时，最后返回后不能改变原链表。

1.暴力

分析：第一遍循环创建节点，构建next指针。第二遍循环找到复制链表的random指针，具体方法是对于每个节点，模板链和复制链从头遍历并且同步移动，当模板链找到当前节点的random节点时，此时复制链指向的节点就是当前节点random应该指向的节点位置。时间复杂度O(n^2)

class Solution {
    public Node copyRandomList(Node head) {
        Node phead=new Node(-1),p=head,q=phead;
        while(p!=null){
            q.next=new Node(p.val);
            q=q.next;
            // q.random=p.random;
            // p.random=p;
            p=p.next;
        }
        p=head;
        q=phead.next;
        while(q!=null){
            Node n1=head,n2=phead.next,ran=p.random;
            while(ran!=null&&n1!=null){
                if(n1==ran){
                    q.random=n2;
                    break;
                }
                n1=n1.next;
                n2=n2.next;
            }
            p=p.next;
            q=q.next;

            
        }
        return phead.next;

    }
}

2.哈希

使用哈希保存模板链每个节点的random指针,目的是最后恢复模板链表。

第一遍遍历时，将模板节点的random指向复制链表的对应位置，然后将复制链表节点的random指针指向同步模板节点的random节点。关键就是同步位置的节点通过模板链random找到。

第二遍遍历，修正复制链的random节点。最后再通过哈希恢复模板链。时间复杂度O(n)

class Solution {
    public Node copyRandomList(Node head) {
        Node phead=new Node(-1),p=head,q=phead;
        Map<Node,Node> map=new HashMap<>();
        while(p!=null){
            q.next=new Node(p.val);
            q=q.next;
            q.random=p.random;
            map.put(p,p.random);
            p.random=q;
            p=p.next;
        }
        p=head;
        q=phead.next;
        while(q!=null){
           if(q.random!=null) q.random=q.random.random;
            q=q.next;
        }
        while(p!=null){
            p.random=map.get(p);
            p=p.next;
        }
        return phead.next;
    }
}