leetcode138.Copy List with Random Pointer

题目要求

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

假设存在这样一个链表，在链表的每一个节点中，除了记录了自身值和指向下一个节点的指针，还有一个随机指针指向链表中任意一个节点。现在要求深度复制这份链表，在不改变原链表内容的情况下，创建一组新的对象，该组对象中的值和原链表中的值相同。

思路一：map

因为任意节点指针的值在一遍遍历中是无法复制的。所以我们可以基本确定至少需要两次遍历才能够充分的复制链表。那么在第一次遍历的时候，我们采用什么样的数据结构来记录第一次遍历的值呢？最直观的思路是使用map，第一次遍历时我们访问next指针，将当前对象和当前对象的复制对象作为key-value值存入map中。第二次遍历时，我们可以一边调整复制对象的next指针，一边调整复制对象的random指针，这两个指针指向的都将是map中源对象的复制对象。所以可以在两次遍历后完成任务。

public RandomListNode copyRandomList(RandomListNode head) {
    if(head==null) return null;
    Map<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
    RandomListNode temp = head;
    while(temp!=null){
        map.put(temp, new RandomListNode(temp.label));
        temp = temp.next;
    }
    
    temp = head;
    while(temp!=null){
        RandomListNode cur = map.get(temp);
        cur.next = map.get(temp.next);
        cur.random = map.get(temp.random);
        temp = temp.next;
    }
    return map.get(head);
}

思路二：利用链表的特性

那么我们有没有可能在不使用map的情况下通过旧节点实现对新节点的检索？答案是肯定的。我们可以充分利用链表的特性来保存对新的复制节点的指针。第一圈遍历时，我们可以将复制的节点插入至被复制的节点的后面。这样我们就可以通过旧节点的next值找到新节点。在第二圈遍历的时候，我们可以依次更新复制节点的random指针，将其指向新的复制节点。最后一圈遍历，我们调整next指针，恢复原链表和塑造新链表。

public RandomListNode copyRandomList2(RandomListNode head) {
    if(head==null) return null;
    RandomListNode current = head, copyHead = null, copyCurrent = null;
    
    while(current!=null){
        RandomListNode temp = new RandomListNode(current.label);
        temp.next = current.next;
        current.next = temp;
        current = current.next.next;
    }
    
    current = head;
    while(current!=null){
        if(current.random!=null){
            current.next.random = current.random.next;
        }
        current = current.next.next;
    }
    
    current = head;
    copyCurrent = copyHead = head.next;
    head.next = head.next.next;
    while(current != null){
        current.next = current.next.next;
        copyCurrent.next = copyCurrent.next.next;
        copyCurrent = copyCurrent.next;
        current = current.next;
    }
    return copyHead;
}