Перестановка соседних узлов в односвязном списке

Условие

Дан односвязный список listHead. Требуется поменять местами каждый соседний узел, образуя пары, и вернуть указатель на новый первый элемент. Если количество узлов нечётное, последний элемент остаётся на месте.

Пример 1: Ввод: listHead = [1,2,3,4] Вывод: [2,1,4,3] Объяснение:

• Пара (1,2) меняется местами → (2,1).
• Пара (3,4) меняется местами → (4,3).
• Итоговый список: [2,1,4,3].

Пример 2: Ввод: listHead = [1,2,3] Вывод: [2,1,3] Объяснение:

• Пара (1,2) меняется местами → (2,1).
• Оставшийся одиночный узел (3) остаётся без изменений.
• Итоговый список: [2,1,3].

Пример 3: Ввод: listHead = [] Вывод: [] Объяснение: Пустой список остаётся пустым, так как нет узлов для перестановки.

Ответ

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

Предполагается стандартный ListNode с полем next:

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

def swap_pairs(head):
    dummy = ListNode(next=head)
    previous = dummy
    while previous.next and previous.next.next:
        first = previous.next
        second = first.next
        first.next = second.next
        second.next = first
        previous.next = second
        previous = first
    return dummy.next

Для пустого списка возвращается None. Время O(n), дополнительная память O(1). Переставляются реальные узлы, что важно, если на них существуют внешние ссылки.