138. Copy List with Random Pointer 发表于 2022-04-12 HashMap12345678910111213141516171819202122class Solution { public Node copyRandomList(Node head) { if (head == null) { return null; } Map<Node, Node> oldToNewMap = new IdentityHashMap<>(); Node node = head; while (node != null) { oldToNewMap.put(node, new Node(node.val)); node = node.next; } for (Map.Entry<Node, Node> entry : oldToNewMap.entrySet()) { Node old = entry.getKey(), duplicate = entry.getValue(); duplicate.next = oldToNewMap.get(old.next); duplicate.random = oldToNewMap.get(old.random); } return oldToNewMap.get(head); }} Linked List1234567891011121314151617181920212223242526272829303132333435363738394041class Solution { public Node copyRandomList(Node head) { if (head == null) { return null; } Node curr = head; while (curr != null) { Node duplicate = new Node(curr.val); Node next = curr.next; curr.next = duplicate; duplicate.next = next; curr = next; } // nodeA -> duplicate nodeA -> nodeB -> duplicate nodeB -> ... curr = head; while (curr != null) { Node duplicate = curr.next; if (curr.random != null) { duplicate.random = curr.random.next; } curr = duplicate.next; } Node duplicateHead = head.next; curr = head; while (curr != null) { Node duplicate = curr.next; Node next = duplicate.next; curr.next = next; if (next != null) { duplicate.next = next.next; } curr = next; } return duplicateHead; }} Reference138. Copy List with Random Pointer剑指 Offer 35. 复杂链表的复制