Задача: 1669. Merge In Between Linked Lists
Сложность: medium

Вам даны два связанных списка: list1 и list2 размером n и m соответственно.

Удалите узлы list1 с ath узла по bth узел и вставьте на их место list2.

Синие ребра и узлы на рисунке в вверху поста указывают на результат:

Пример:

Input: list1 = [10,1,13,6,9,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
Output: [10,1,13,1000000,1000001,1000002,5]
Explanation: We remove the nodes 3 and 4 and put the entire list2 in their place. The blue edges and nodes in the above figure indicate the result.

👨‍💻 Алгоритм:

1⃣Инициализация и добавление узлов из list1 до узла a в массив:

Инициализировать переменную index равную 0 и current1 равную list1.
Пока index меньше a, добавлять current1.val в массив mergeArray, перемещаться к следующему узлу current1.next и увеличивать index.

2⃣Добавление узлов из list2 в массив:
Инициализировать current2 равную list2.
Пока current2 не равен null, добавлять current2.val в mergeArray и перемещаться к следующему узлу current2.next.

3⃣Добавление узлов из list1 от узла b + 1 до конца в массив и создание нового связанного списка:
Найти узел на позиции b + 1, перемещая current1 и увеличивая index, пока index меньше b + 1.
Добавлять узлы из current1 в массив, пока current1 не станет null.
Создать новый связанный список из значений в mergeArray, добавляя узлы в начало списка и возвращая его.

😎 Решение:

class Solution {
    function mergeInBetween($list1, $a, $b, $list2) {
        $mergeArray = [];
        $index = 0;
        $current1 = $list1;
        
        while ($index < $a) {
            $mergeArray[] = $current1->val;
            $current1 = $current1->next;
            $index++;
        }
        
        $current2 = $list2;
        while ($current2 !== null) {
            $mergeArray[] = $current2->val;
            $current2 = $current2->next;
        }
        
        while ($index < $b + 1) {
            $current1 = $current1->next;
            $index++;
        }
        
        while ($current1 !== null) {
            $mergeArray[] = $current1->val;
            $current1 = $current1->next;
        }
        
        $resultList = null;
        for ($i = count($mergeArray) - 1; $i >= 0; $i--) {
            $resultList = new ListNode($mergeArray[$i], $resultList);
        }
        
        return $resultList;
    }
}

Ставь 👍 и забирай 📚 Базу знаний