Всем привет,

Это пятый день решения проблем с JavaScript.

Сегодня я объясню решение проблемы Объединить два отсортированных списка в LeetCode.

Что такое проблема объединения двух отсортированных списков?

Вам даны главы двух отсортированных связанных списков list1 и list2.

Объедините два списка в один отсортированный список. Список должен быть составлен путем соединения узлов первых двух списков.

Возвращает заголовок объединенного связанного списка.

Пример:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Решение

Ссылка на репозиторий GitHub — https://github.com/Starboy369/JSProblemSolving (Отметьте мой репозиторий звездочкой, чтобы найти все решения на JavaScript)

Фрагмент кода

var mergeTwoLists = function(l1, l2) {
    let tempNode = new ListNode(0, null);
    let currentNode = tempNode;
    
    while (l1 && l2) {
        if(l1.val < l2.val) {
            currentNode.next = l1;
            l1 = l1.next
        } else {
            currentNode.next = l2;
            l2 = l2.next
        }
        currentNode = currentNode.next;
    }
    currentNode.next = l1 || l2;
    
    return tempNode.next;
};

Используемые понятия

  1. Список — упорядоченный список значений. List поддерживается двусвязным списком с головным узлом. Список имеет свойство head на пустой узел. Список начинается с узла head с доступным узлом next. Последним узлом в списке является узел prev из узла head. head представляет узел, следующий за концом списка, и не имеет value.
  2. List.val — возвращает первый элемент списка. [1,2,3,4,5].val возвращает 1 .
  3. List.next — возвращает остальные элементы при перемещении головы вперед.

Пояснение кода

Мы создаем временный список и устанавливаем заголовок на ноль. Когда заданы условия в цикле while, происходит следующее:

Шаг 1

Темп = 0 || Список 1= 1->2->4 || Список 2 = 1->3->4

List 1 val = 1 и List 2 val = 1, поэтому условие входит в else

temp.next = список 2, поэтому temp = 0->1->3->4

список 2 = список2.следующий = 3->4

Шаг 2

темп = 0->1(следующий)->3->4 || Список 1= 1-›2-›4|| Список 2 = 3->4

List 1 val = 1 и List 2 val = 3, поэтому условие выполнено

temp.next = список 1, поэтому temp = 0->1->1->2->3

список 1= список1.следующий = 2->3

Шаг 3

темп =0->1->1(следующий)->2->3 || Список 1= 2->4 || Список 2 = 3->4

List 1 val = 2 и List 2 val = 3, поэтому условие выполнено

temp.next = список 1, поэтому temp = 0->1->1->2->4

список 1= список1.следующий = 4

Шаг 4

темп =0->1->1->2(следующий)->4 || Список 1= 4 || Список 2 = 3->4

List 1 val = 4 и List 2 val = 3, поэтому условие входит в else

temp.next = список 2, поэтому temp = 0->1->1->2->3->4

список 2= список2.следующий=4

Шаг 5

темп =0->1->1->2->3(следующий)->4 || Список 1= 4 || Список 2 = 3->4

List 1 val = 4 и List 2 val = 4, поэтому условие входит в else

temp.next = список 2, поэтому temp = 0->1->1->2->3->4

список 2 = список2.следующий = ноль

теперь условие while не выполняется.

currentNode.next = l1 || l2;

приведенная выше строка кода изменяет температуру на 0->1->1->2->3->4->4

и функция возвращает temp.next == › 1-›1-›2-›3-›4-›4

Заключение

Описанным выше способом мы можем решить эту проблему, используя концепции List Val и Next.

И, как обычно, дайте мне знать, если есть лучший подход к решению этой проблемы. Рад учиться у всех вас!

Я буду каждый день публиковать блоги с проблемами, решенными в JavaScript. Следуйте за мной, чтобы никогда не пропустить решение.

Удачного кодирования на JavaScript!!!