Задача: 148. Sort List
Сложность: Medium

Дан указатель на начало связанного списка. Верните список после его сортировки в порядке возрастания.

Пример:

Input: head = [4,2,1,3]
Output: [1,2,3,4]

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

1⃣Разделение списка (Фаза разделения):
Рекурсивно разделяйте исходный список на две половины. Процесс разделения продолжается до тех пор, пока в связанном списке не останется только один узел. Для разделения списка на две части используется подход с быстрым и медленным указателями, как упоминается в методе поиска середины связанного списка.

2⃣Сортировка подсписков и их объединение (Фаза слияния):
Рекурсивно сортируйте каждый подсписок и объединяйте их в один отсортированный список. Это аналогично задаче слияния двух отсортированных связанных списков.

3⃣Иллюстрация процесса сортировки:
Процесс продолжается до тех пор, пока не будет получен исходный список в отсортированном порядке. Например, для связанного списка [10,1,60,30,5] описан процесс сортировки слиянием с использованием подхода сверху вниз. Если у нас есть отсортированные списки list1 = [1,10] и list2 = [5,30,60], следующая анимация иллюстрирует процесс слияния обоих списков в один отсортированный список.

😎 Решение:

class ListNode {
    public $val;
    public $next;

    public function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}

class Solution {
    public function sortList($head) {
        if ($head === null || $head->next === null) {
            return $head;
        }
        $mid = $this->getMid($head);
        $left = $this->sortList($head);
        $right = $this->sortList($mid);
        return $this->merge($left, $right);
    }

    private function merge($list1, $list2) {
        $dummyHead = new ListNode();
        $tail = $dummyHead;
        while ($list1 !== null && $list2 !== null) {
            if ($list1->val < $list2->val) {
                $tail->next = $list1;
                $list1 = $list1->next;
            } else {
                $tail->next = $list2;
                $list2 = $list2->next;
            }
            $tail = $tail->next;
        }
        $tail->next = $list1 ?? $list2;
        return $dummyHead->next;
    }

    private function getMid($head) {
        $midPrev = null;
        $slow = $head;
        $fast = $head;
        while ($fast !== null && $fast->next !== null) {
            $midPrev = ($midPrev === null) ? $slow : $midPrev->next;
            $slow = $slow->next;
            $fast = $fast->next->next;
        }
        $mid = $midPrev->next;
        $midPrev->next = null;
        return $mid;
    }
}

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