原题链接: 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