Se proporciona una lista vinculada de modo que cada nodo contiene un puntero aleatorio adicional que podría apuntar a cualquier nodo de la lista o nulo.
Devuelve una copia profunda de la lista.
Solución Java 1
Podemos solucionar este problema siguiendo los siguientes pasos:
- copiar cada nodo, es decir, duplicar cada nodo e insertarlo en la lista
- copiar punteros aleatorios para todos los nodos recién creados
- romper la lista a dos
public RandomListNode copyRandomList(RandomListNode head) { if (head == null) return null; RandomListNode p = head; // copy every node and insert to list while (p != null) { RandomListNode copy = new RandomListNode(p.label); copy.next = p.next; p.next = copy; p = copy.next; } // copy random pointer for each new node p = head; while (p != null) { if (p.random != null) p.next.random = p.random.next; p = p.next.next; } // break list to two p = head; RandomListNode newHead = head.next; while (p != null) { RandomListNode temp = p.next; p.next = temp.next; if (temp.next != null) temp.next = temp.next.next; p = p.next; } return newHead; } |
La parte de la lista de interrupciones anterior mueve el puntero 2 pasos cada vez, también puede mover uno a la vez, lo que es más simple, como el siguiente:
while(p != null && p.next != null){ RandomListNode temp = p.next; p.next = temp.next; p = temp; } |
Solución Java 2: uso de HashMap
Del comentario de Xiaomeng a continuación, podemos usar un HashMap que lo hace más simple.
public RandomListNode copyRandomList(RandomListNode head) { if (head == null) return null; HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>(); RandomListNode newHead = new RandomListNode(head.label); RandomListNode p = head; RandomListNode q = newHead; map.put(head, newHead); p = p.next; while (p != null) { RandomListNode temp = new RandomListNode(p.label); map.put(p, temp); q.next = temp; q = temp; p = p.next; } p = head; q = newHead; while (p != null) { if (p.random != null) q.random = map.get(p.random); else q.random = null; p = p.next; q = q.next; } return newHead; } |
