138. Copy List with Random Pointer

Leetcode Hash Table Linked List

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.

Definition for singly-linked list with a random pointer.

class RandomListNode {
    int label;
    RandomListNode next, random;
    RandomListNode(int x) { this.label = x; }
};

分析

复制带随机指针的链表。第一种方法可以借鉴LeetCode133 Clone Graph:

• 从head开始遍历链表
• 如果链表的节点是未曾访问的，复制该节点，并放入哈希表中
• 如果链表的节点已经被访问过，则从哈希表中取出该节点
• 让random和next指向正确的节点

该方法的时间和空间复杂度是$O(n)。

public RandomListNode copyRandomList(RandomListNode head) {
    Map<Integer, RandomListNode> map = new HashMap<>();
    return copyRandomList(map, head);
}

private RandomListNode copyRandomList(Map<Integer, RandomListNode> map, RandomListNode head) {
    if (head == null) return null;
    if (map.containsKey(head.label)) return map.get(head.label);
    RandomListNode newHead = new RandomListNode(head.label);
    map.put(head.label, newHead);
    newHead.next = copyRandomList(map, head.next);
    newHead.random = copyRandomList(map, head.random);
    return newHead;
}

上面的方法是比较通用的方法，把链表看成是图的一种，但是没有利用到链表的特性。

为了方便的寻找到新创建的节点，可以将新创建(复制)的节点放置于原节点之后，使原始节点和复制节点交错分布：

• 向前遍历链表，将复制节点放置于原节点之后
• 将复制节点的random指向正确的位置
• 分离链表

public RandomListNode copyRandomList(RandomListNode head) {
    if (head == null) return null;
    // 遍历链表，复制节点，形成原节点和复制节点的交错分布
    RandomListNode originalNode = head;
    RandomListNode clonedNode;
    while (originalNode != null) {
        // 创建新节点
        clonedNode = new RandomListNode(originalNode.label);
        // 指向正确位置
        clonedNode.next = originalNode.next;
        originalNode.next = clonedNode;
        // 前进一个节点
        originalNode = clonedNode.next;
    }

    // 遍历链表，使ranom指针指向正确位置
    originalNode = head;
    while (originalNode != null) {
        // random可能是null，由于originalNode.next.random默认是null，所以不设置
        if (originalNode.random != null) 
                originalNode.next.random = originalNode.random.next;
        originalNode = originalNode.next.next;
    }

    // 分离链表
    originalNode = head;
    clonedNode = originalNode.next;
    RandomListNode clonedHead = clonedNode;
    while (originalNode.next.next != null) {
        originalNode.next = clonedNode.next;
        originalNode = originalNode.next;
        clonedNode.next = originalNode.next;
        clonedNode = clonedNode.next;
    }
    // 结束原链表
    originalNode.next = null;
    return clonedHead;
}