publicclassSolution{ public RandomListNode copyRandomList(RandomListNode head){ RandomListNode cur = head, next, prev; // copy the nodes one by one, into the old new // old-new-old-new-old-new... while (cur != null) { next = cur.next; cur.next = new RandomListNode(cur.label); cur.next.next = next; cur = next; } // copy random node cur = head; while (cur != null) { if (cur.random != null) cur.next.random = cur.random.next; cur = cur.next.next; } // split new nodes from old ones RandomListNode newHead = new RandomListNode(0); prev = newHead; while (head != null) { prev.next = head.next; head.next = head.next.next; head = head.next; prev = prev.next; } return newHead.next; } }
Recursive solution with a global variable
1 2 3 4 5 6 7 8 9 10 11 12
publicclassSolution{ Map<RandomListNode, RandomListNode> oldToNew = new HashMap<>(); public RandomListNode copyRandomList(RandomListNode head){ if (head == null) returnnull; if (oldToNew.containsKey(head)) return oldToNew.get(head); RandomListNode result = new RandomListNode(head.label); oldToNew.put(head, result); result.next = copyRandomList(head.next); result.random = copyRandomList(head.random); return result; } }