Задача: 86. Partition List
Сложность: medium

Дана голова связного списка и значение x. Разделите его так, чтобы все узлы с значениями меньше x находились перед узлами с значениями, равными или большими x.

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

Пример:

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

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

1⃣Инициализация указателей: Создайте два указателя before и after, каждый из которых инициализирован временным (dummy) узлом. Это упрощает управление границами списка, минимизируя необходимость проверок условий в коде.

2⃣Итерация по исходному связному списку: Перемещайте каждый узел в список before, если его значение меньше x, и в список after, если его значение равно или больше x. Это сохраняет относительный порядок узлов в каждой из двух частей.

3⃣Соединение списков: После обработки всех узлов исходного списка, соедините списки before и after. Удалите временные узлы в начале каждого списка перед их соединением, чтобы исключить их из итогового связного списка.

😎 Решение:

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

function partition($head, $x) {
    $before_head = new ListNode(0);
    $before = $before_head;
    $after_head = new ListNode(0);
    $after = $after_head;
    
    while ($head != null) {
        if ($head->val < $x) {
            $before->next = $head;
            $before = $before->next;
        } else {
            $after->next = $head;
            $after = $after->next;
        }
        $head = $head->next;
    }
    $after->next = null;
    $before->next = $after_head->next;
    
    return $before_head->next;
}

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