力扣-138.随机链表的复制

题目链接

138.随机链表的复制

解法一：哈希表+递归复制

class Solution {HashMap<Node, Node> map = new LinkedHashMap<>();public Node copyRandomList(Node head) {if (head == null) {return null;}if (!map.containsKey(head)) {Node headNew = new Node(head.val);map.put(head, headNew);headNew.next = copyRandomList(head.next);headNew.random = copyRandomList(head.random);}return map.get(head);}
}

小结：如果遍历过程中遇到任何一个节点没有被创建，立刻递归地进行创建。

解法二：哈希表+迭代

public Node copyRandomList(Node head) {if (head == null) return null;HashMap<Node, Node> map = new HashMap<>();Node curr = head;// 第一遍遍历：创建所有新节点 while (curr != null) {map.put(curr,  new Node(curr.val)); curr = curr.next; }// 第二遍遍历：连接 next 和 random curr = head;while (curr != null) {map.get(curr).next  = map.get(curr.next); map.get(curr).random  = map.get(curr.random); curr = curr.next; }return map.get(head); 
}

小结：解法一的迭代写法，更加清晰易懂。

解法三：迭代+结点拆分

• 详见这里

小结：

1. 复制各节点，并构建拼接链表，形如7->7->3->3->…
2. 构建各新节点的 random 指向
3. 拆分两链表