Блог

Главная - Вопросы по программированию - У меня есть быстрый вопрос о том, как работает этот связанный код слияния списков

У меня есть быстрый вопрос о том, как работает этот связанный код слияния списков

#javascript #algorithm #linked-list

#javascript #алгоритм #связанный список

Вопрос:

Я в замешательстве от того, как head.next возвращает весь список вместо следующего значения, такого как l1, l2, dummy .next, в приведенном ниже коде. в частности, мне интересно, как head.next возвращает весь отсортированный массив и пропускает значение -1, которое было введено во второй строке.

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

  while (l1 !== null amp;amp; 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;
  }
}

Комментарии:

1. Возврат head.next , очевидно, пропускает первый узел. Он не возвращает отсортированный список. Он возвращает специально объединенный список, который оказывается отсортированным, если оба входных списка уже отсортированы.

2. таким образом, он пропускает первый узел и возвращает остальные узлы?

3. Он возвращает узел, у которого есть next ключ, который может связать другой узел.

Ответ №1:

Возможно, это помогает при визуализации построения списка:

Пусть входным сигналом будет список со значениями [3, 9], а другой — только [4]:

  l1
 ↓
 3 → 9 → null

 l2
 ↓
 4 → null

Перед запуском цикла создается новый узел:

 head
 ↓
-1
 ↑
dummy

Цикл выполнит свою первую итерацию, и if условие истинно. Первый dummmy.next адаптирован, что приводит к такой ситуации:

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

 l2
 ↓
 4 → null

… и затем l1 переназначается новая ссылка:

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

 l2
 ↓
 4 → null

Последний оператор в цикле присваивает новую ссылку на dummy :

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

 l2
 ↓
 4 → null

Цикл повторяется во второй раз, и if теперь условие равно false, поэтому мы попадаем в else блок. Первый dummmy.next адаптирован (это разрывает связь, с которой он был l1 , и поэтому я перемещаю визуализацию l1 и l2 ):

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

 l1
 ↓
 9 → null

… и затем l1 переназначается новая ссылка, в этом случае она становится null :

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

 l1
 ↓
 9 → null

Последний оператор в цикле присваивает новую ссылку на dummy :

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

 l1
 ↓
 9 → null

На этом этапе условие цикла больше не выполняется ( l2 is null ), и поэтому if выполняется блок, который следует за циклом. Это связано dummy.next с оставшейся (не null ) ссылкой. Опять же, ради визуализации я меняю положение l1 и l2 :

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

 l2
 ↓
null

Теперь мы переходим к последнему утверждению : return head.next . Обратите внимание, что head он никогда не отходил от нового узла, который был создан в начале.

Итак, возвращаемая ссылка:

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

 l2
 ↓
null

Обратите внимание, как head он продолжает указывать на узел с -1 в течение всего выполнения этой функции. Временный узел со значением -1 будет собран мусором, поскольку после возврата функции на него больше не будет ссылаться переменная ( head это локальная переменная).

Комментарии:

1. Я действительно ценю ваше время