LeetCode - 138 Copy List with Random Pointer

作者 QIFAN 日期 2017-01-23
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