Así que este es un problema de LeetCode . El objetivo principal es fusionar dos listas ordenadas, pero ese no es el problema. Busqué la solución a continuación y estoy realmente confundido por dos razones.
Traté de entenderlo, sin embargo, no pude entender la lógica. Imprimo declaraciones para ver qué está pasando debajo del capó y todavía me confunde por qué hacemos node.next = new ListNode(list1.val);
en lugar de node = new ListNode(list1.val);
. Usando node = new ListNode(list1.val);
devuelve una lista vacía y no sé por qué
var mergeTwoLists = function (list1, list2) { const head = new ListNode(0); let node = head; while (list1 !== null || list2 !== null) { if (list2 === null || (list1 !== null && list1.val <= list2.val)) { node.next = new ListNode(list1.val); list1 = list1.next; } else { node.next = new ListNode(list2.val); list2 = list2.next; } node = node.next; } return head.next; };
¿Por qué estamos usando una cabeza ficticia?
Para simplificar el código en el bucle. Se puede hacer sin dummy, pero entonces el código se vería así:
let head = null; // no dummy let node = head; while (list1 !== null || list2 !== null) { if (list2 === null || (list1 !== null && list1.val <= list2.val)) { if (node == null) { // First time only -- need to assign to head head = new ListNode(list1.val); } else { // all other times: node.next = new ListNode(list1.val); } list1 = list1.next; } else { if (node == null) { // First time only -- need to assign to head head = new ListNode(list2.val); } else { // all other times: node.next = new ListNode(list2.val); } list2 = list2.next; } node = node.next; } return head; // There's no dummy, so return real head
Tenga en cuenta cómo debemos distinguir dentro del bucle entre el caso en el que aún no tenemos el nodo principal y debemos asignarle, y todos los demás casos. Con la introducción de un nodo ficticio, esta distinción no es necesaria en el bucle, y después del bucle podemos omitir ese nodo ficticio para encontrar la cabeza real ( head.next
).
¿Por qué asignamos al siguiente nodo en lugar del actual?
Para crear una lista vinculada, debe asignar a los next
atributos de los nodos. Si no asigna a los next
atributos, sino a las variables, no se crea ninguna lista. Si simplemente hace node = new ListNode((list2.val)
, crea un nodo y lo asigna a una variable, pero no se convierte en parte de una lista vinculada más grande. Peor aún, cuando en una próxima iteración vuelve a hacer esto , pierde la referencia al nodo anterior que se creó en la iteración anterior; no hay forma de recuperarlo.