Share my java solution

  • 0

    The solution using a Map which is slow and space expensive. A better solution reuses the links to copy the random links without using extra map or array.

    To do that, for each node, we create a copy copyNode and we rewire the nodes so that is and is copyNode. In other words,

    • given 1->2->3->4
    • becomes 1->1->2->2->3->3->4->4

    Now, we can traversal this "doubled" list again. This time, we copy the random links for the copied nodes. After that, we just need to separate the list into two lists, odd and even, which is the same as the "Odd Even Linked List" except we do not connect even to odd in the end. Instead, we set the odd tail to null.

    I didn't look at the posted solutions when I do this problem. Apparently the idea is the same. But I think the implement is a bit different so I posted this anyway. Hope it helps.


    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) return null;
        for (RandomListNode iter = head; iter != null; iter = {
            RandomListNode copy = new RandomListNode(iter.label);
   = copy;
        for (RandomListNode iter = head; iter != null; iter =
            if (iter.random != null)
        RandomListNode evenHead =, odd = head, even = evenHead
        while ( != null) {
            odd =;
            even =;
        } = null;
        return evenHead;

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.