Estoy confundido sobre cómo head.next devuelve la lista completa en lugar de un valor siguiente como l1, l2, dummy .next en el código siguiente. en particular, me pregunto cómo head.next devuelve una matriz ordenada completa y omite el valor -1 que se ingresó en la segunda línea.

let mergeTwoLists = function (l1, l2) {
  let dummy = new ListNode(-1);
  let head = dummy;

  while (l1 !== null && l2 !== null) {
    if (l1.val <= l2.val) {
      dummy.next = l1;
      l1 = l1.next;
    } else {
      dummy.next = l2;
      l2 = l2.next;
    }
    dummy = dummy.next;
  }

  if (l1 !== null) {
    dummy.next = l1;
  } else {
    dummy.next = l2;
  }

  return head.next;
};

class ListNode {
  constructor(val = null, next = null) {
    this.val = val;
    this.next = next;
  }
}
0
Tyrique Daniel 26 oct. 2020 a las 02:46

1 respuesta

La mejor respuesta

Quizás ayude a visualizar cómo se construye la lista:

Sea la entrada una lista con valores [3, 9] y otra con solo [4]:

 l1
 ↓
 3 → 9 → null

 l2
 ↓
 4 → null

Antes de que comience el ciclo, se crea un nuevo nodo:

head
 ↓
-1
 ↑
dummy

El ciclo hará su primera iteración y la condición if es verdadera. Primero se adapta dummmy.next, lo que conduce a esta situación:

head l1
 ↓   ↓
-1 → 3 → 9 → null
 ↑
dummy    

 l2
 ↓
 4 → null

... y luego a l1 se le reasigna una nueva referencia:

head     l1
 ↓       ↓
-1 → 3 → 9 → null
 ↑
dummy    

 l2
 ↓
 4 → null

La última declaración del ciclo asigna una nueva referencia a dummy:

head     l1
 ↓       ↓
-1 → 3 → 9 → null
     ↑
    dummy    

 l2
 ↓
 4 → null

El ciclo se repite una segunda vez y la condición if ahora es falsa, por lo que obtenemos el bloque else. Primero se adapta dummmy.next (esto rompe el vínculo que tenía con l1, por lo que muevo la visualización de l1 y l2):

head     l2
 ↓       ↓
-1 → 3 → 4 → null
     ↑
    dummy    

 l1
 ↓
 9 → null

... y luego l1 se reasigna una nueva referencia, en este caso se convierte en null:

head          l2
 ↓            ↓
-1 → 3 → 4 → null
     ↑
    dummy    

 l1
 ↓
 9 → null

La última declaración del ciclo asigna una nueva referencia a dummy:

head          l2
 ↓            ↓
-1 → 3 → 4 → null
         ↑
        dummy    

 l1
 ↓
 9 → null

En esta etapa, la condición del bucle ya no es verdadera (l2 es null), por lo que se ejecuta el bloque if que sigue al bucle. Esto vincula dummy.next con la referencia restante (no null). Nuevamente, por el bien de la visualización, cambio la posición de l1 y l2:

head         l1
 ↓           ↓
-1 → 3 → 4 → 9 → null
         ↑
        dummy    

 l2
 ↓
null

Ahora llegamos a la declaración final: return head.next. Observe cómo head no nunca se alejó del nuevo nodo que se creó al principio.

Entonces la referencia devuelta es:

head         l1
 ↓           ↓
-1 → 3 → 4 → 9 → null
     ↑
    returned    

 l2
 ↓
null

Observe cómo head sigue apuntando al nodo con -1 durante toda la ejecución de esta función. El nodo temporal con valor -1 será recolectado como basura, ya que no hay ninguna variable que haga referencia a él una vez que la función haya regresado (head es una variable local ).

2
trincot 26 oct. 2020 a las 10:10