328. Odd Even Linked List

LeetCode задача 328

Задача

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

Вариант решения 1

Рассмотрим вариант решения более простой для понимания и реализации.

Подсказки

Использовать два связных списка.

Подход

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

В конце прохода список с четными узлами добавить в конец списка с нечетными узлами.

Алгоритм

1. Объявляем 2 пустых связных списка (even_head, odd_head)
2. Объявляем два указателя на каждый список (even,`odd). Данные указатели будут перемещаться по своим спискам.
3. Проходим по списку head:
   1. если текущий указатель - четный, добавляем его в even_head (обновляем значение указателя списка).
   2. Переставляем указатель на следующий. even = even.next
   3. Шаги 1-2 для нечетного указателя соответсвенно.
4. Переходим к следующему указателю в head.
5. Соединяем два списка. Список с четные указателями становится следующим после списка с нечетными указателями.
   1. Так как четные указатели должны стоять в самом конце нового списка, то обновляем even.next = None, потому что после него ничего не должно идти.
   2. Добавляем even_head к списку odd_head в конец.
6. Возвращаем odd_head

Решение

class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        odd_head = ListNode(0)
        even_head = ListNode(0)

        odd = odd_head
        even = even_head
        is_odd = True
        while head:
            if is_odd:
                odd.next = head
                odd = odd.next
            else:
                even.next = head
                even = even.next

            head = head.next    
            is_odd = not is_odd
        
        even.next = None  # самый последний узел
        odd.next = even_head.next # head в конец списка

        return odd_head.next

Вариант решения 2

Подсказки

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

Подход

Абстрактная идея:

• превратить список head в список из нечетных по счету узлов.
• превратить список even_head из списка head с содержанием только четных узлов

1. Инициализация указателей: Инициализируем указатели для нечетных и четных узлов, а также сохраняем начальный четный узел, который будет использован после того, как пройдем весь список.
2. Перестановка узлов: Проходим по списку, меняя местами нечетные и четные узлы.
   1. Обновляем next для нечетного путем взятия next у четного: odd.next = even.next
   2. Перемещаем указатель для нечетного вперед: odd = odd.next
   3. 1 и 2 шаги проделываем для четного указателя. 💡 четный указатель обновляет ссылки с обновленного четного указателя.
3. Соединение списков: После того как все узлы переставлены, последний нечетный узел должен указывать на первый четный узел.

Пример для 1,2,3,4,5:

1. Инициализация указателей:

• Указатель odd указывает на узел с значением 1. состояние списка: 1-2-3-4-5
• Указатель even указывает на узел с значением 2. состояние списка: 2-3-4-5
• Указатель even_head указывает на узел с значением 2. состояние списка: 2-3-4-5

2. Первый проход:

• odd.next будет указывать на узел, следующий за even: 1-2 => 1-3, odd.next = 3.
• Обновляем odd на odd.next. odd = 3, odd.next = 4.
• even.next будет указывать на узел, следующий за новым odd: 2-3 => 2->4, even.next = 4.
• Перемещаем even на even.next
• Текущее состояние списков head: 1-3-4-5, even_head: 2-4-5

3. Второй проход:

• odd.next будет указывать на узел, следующий за even (узел с значением 6)
• Обновляем odd на odd.next. с значением 6
• even.next будет указывать на узел, следующий за новым odd (узел с значением 5)
• Перемещаем even на узел с значением 5
• Текущее состояние списка: 1-3-5. 2-4

4. Объединение четных и нечетных:

После окончания всех проходов, установить odd.next на узел, на который указывает even_head.

Алгоритм

1. Инициализируем указатели odd и even на начальные нечетные и четные узлы.
2. Сохраняем начальный четный узел в переменной even_head.
3. Пока четные и нечетные узлы не None, продолжаем перестановку.
4. В конце соединяем последний нечетный узел с even_head.

Решение

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def oddEvenList(head: ListNode) -> ListNode:
    if not head:
        return head
    
    odd = head
    even = head.next

    even_head = even
    
    while even and even.next:
        odd.next = even.next
        odd = odd.next
        even.next = odd.next
        even = even.next
    
    # Соединяем последний нечетный узел с первым четным
    odd.next = even_head
    
    return head