LeetCode - 138 Copy List with Random Pointer

原题链接： 138. Copy List with Random Pointer

题干

给定一个链表，每一个节点都包含一个指向任意一个节点或 null 的指针。要求 deep copy 这个链表。

思路

要复制普通的指针很简单，如果每次都复制 next 与 random 指针，那如果判断不会重复？直接的方式就是使用 HashTable 。

我的思路就是：

按顺序遍历链表，检查 Map 是否已经存在 next 与 random ，
- 若不存在，复制新的 nextNew 与 randomNew ，并将 (random, randomNew) 作为键值对存入 Map 。
- 若存在，则根据情况将当前节点 curr 的指针设置好。

时间复杂度 $O(N)$ ，空间复杂度 $O(N)$ 。

代码：

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public RandomListNode copyRandomList(RandomListNode head) {
    if (head == null) {
        return null;
    }
    RandomListNode copyHead = new RandomListNode(head.label);
    HashMap<RandomListNode, RandomListNode> map = new HashMap<>();
    RandomListNode curr = head;
    RandomListNode copyCurr = copyHead;
    map.put(curr, copyCurr);
    while (curr != null) {
        copyCurr.next = copyNode(map, curr.next);
        copyCurr.random = copyNode(map, curr.random);
        curr = curr.next;
        copyCurr = copyCurr.next;
    }
    return copyHead;    
}
private RandomListNode copyNode(HashMap<RandomListNode, RandomListNode> map, RandomListNode pointTo) {
    if (pointTo == null) {
        return null;
    }
    if (!map.containsKey(pointTo)) {
        map.put(pointTo, new RandomListNode(pointTo.label));
    }
    return map.get(pointTo);
}

其他思路： Copy List with Random Pointer

题干
思路

LeetCode - 138 Copy List with Random Pointer

题干

思路

FEATURED TAGS

FRIENDS