Java Solution - BFS (Queue + Map)


  • 0

    Should be self-explanatory. Thanks.

    public class Solution {
        public RandomListNode copyRandomList(RandomListNode head) {
            if (head == null) return null; 
            RandomListNode res = new RandomListNode(head.label); 
            
            Queue<RandomListNode> q = new LinkedList<>(); 
            Map<RandomListNode, RandomListNode> map = new HashMap<>(); 
            
            q.add(head); // add values to queue and map
            map.put(head, res); 
            
            while (!q.isEmpty()) {
                RandomListNode cur = q.poll(); 
                if (cur.next != null && !map.containsKey(cur.next)) { //clone next 
                    map.put(cur.next, new RandomListNode(cur.next.label));
                    q.offer(cur.next); 
                }
                map.get(cur).next = map.get(cur.next); //connect the nodes in the cloned graph 
    
                if (cur.random != null && !map.containsKey(cur.random)) { //clone random 
                    map.put(cur.random, new RandomListNode(cur.random.label));
                    q.offer(cur.random); 
                }
                map.get(cur).random = map.get(cur.random); // connect the nodes in the cloned graph 
            }
            
            return res; 
        }
    }

Log in to reply
 

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