Решение задачи LeetCode: Merge Two Sorted Lists

Обзор задачи

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

Установка

Пакет доступен на Packagist и устанавливается через Composer:

composer require evgeny87/leetcode-task

Архитектурные принципы

При реализации были соблюдены следующие стандарты:

• Immutability: Сервис объявлен как final readonly (стандарт PHP 8.4+).
• DI & Clean Code: Строгое соблюдение PSR-12, использование Constructor Injection и отказ от статических методов.
• Алгоритмические "Три кита":
  1. Использование указателей для навигации.
  2. Чистые условные выражения без оператора "!".
  3. Цикл while для итерации по связанным спискам.

Структура проекта

leetcode-task/
├── src/
│   ├── Service/
│   │   └── MergeService.php       # Бизнес-логика (слияние двумя методами)
│   ├── DTO/
│   │   └── ListNode.php           # Объект данных (узлы списка)
│   └── Exceptions/
│       └── ListEmptyException.php # Кастомные ошибки
├── README.md                      # Документация и анализ с описание и обоснование сложности
└── composer.json                  # Автозагрузка PSR-4

Обоснование сложности алгоритмов

1. Вариант In-Place (Алгоритмический)

   • Сложность по времени (T): O(n + m), где n и m — количество узлов в списках. Мы совершаем один линейный проход по элементам (слайды 10, 43).
   • Сложность по памяти (M): O(1). Алгоритм не выделяет память под новые элементы, работая исключительно с перестановкой указателей существующих объектов в памяти (splicing).

2. Вариант Immutable (Архитектурный)

   • Сложность по времени (T): O(n + m). Аналогичный линейный проход.
   • Сложность по памяти (M): O(n + m). Алгоритм создает полностью новые объекты ListNode для результирующего списка.

Зачем использованы два метода?

В данной работе реализовано два подхода для демонстрации понимания различных сценариев разработки:

1. Демонстрация эффективности (In-Place): Этот метод ориентирован на максимальную производительность и минимальное потребление ресурсов. Он идеально подходит для алгоритмических соревнований (LeetCode), где критичны лимиты памяти.
2. Демонстрация чистоты архитектуры (Immutable): Этот метод следует принципу No Side Effects. В реальных энтерпрайз-системах (The evgeny87 Way) важно, чтобы входные данные оставались неизменными. Использование Immutable-подхода гарантирует, что исходные списки не будут "испорчены" в процессе слияния, что предотвращает трудноуловимые баги в других частях системы, которые могут использовать те же объекты.