Neat Solution with DFS


  • 0
    A

    We can treat a linked list with a random pointer as a graph, so similar to using DFS to clone a graph, we can use DFS to create this linked list.

     public RandomListNode copyRandomList(RandomListNode head) {
        Map<RandomListNode, RandomListNode> nodeMap = new HashMap<RandomListNode, RandomListNode>();
        return copyRandomList(head, nodeMap);
    }
    
    public RandomListNode copyRandomList(RandomListNode head, Map<RandomListNode, RandomListNode> nodeMap) {
        if (head == null) {
            return null;
        }
        if (nodeMap.containsKey(head)) {
            return nodeMap.get(head);
        }
        
        RandomListNode node = new RandomListNode(head.label);
        nodeMap.put(head, node);
        node.next = copyRandomList(head.next, nodeMap);
        node.random = copyRandomList(head.random, nodeMap);
        return node;
    }

  • 0
    O

    Well, your solution may be correct. But DFS uses too much space. A constant space is enough for this question.


  • 0
    A

    Yes. You're right. But I don't think it will use more than O(N) space because it will not recurse more than N times. I don't know if you're talking about the constant space solution in the leetcode book, I looked through it, but I just feel it is not quite straightforward.


  • 0
    W

    I think O(n) space is acceptable. May be we can use unordered_map to make a little progress, instead of map.


  • 0
    Q

    You said you can solve it with constant space, could you please show your code?


Log in to reply
 

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