В этой статье блога мы углубимся в проблему перемещения хвоста связанного списка в его начало. Мы рассмотрим различные методы решения этой задачи и предоставим примеры кода на Python. К концу у вас будет полное понимание проблемы и различные подходы к ее решению.

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

Пример:
Рассмотрим следующий связанный список:
1 ->2 ->3 ->4 ->5

После перемещения хвоста в голову обновленный связанный список должен иметь следующий вид:
5 ->1 ->2 ->3 ->4

Метод 1: наивный подход
Самый простой подход предполагает обход всего связанного списка в поисках предпоследнего узла и последнего узла. Затем мы соответствующим образом обновляем указатели.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
def move_tail_to_head(head):
    if not head or not head.next:
        return head
    curr = head
    prev = None
    while curr.next:
        prev = curr
        curr = curr.next
    curr.next = head
    prev.next = None
    return curr

Временная сложность: O(n), где n — количество узлов в связанном списке.

Метод 2: эффективный подход с двумя указателями
Чтобы избежать повторного обхода связанного списка, мы можем использовать два указателя: один из них опережает другой на k узлов. Как только первый указатель достигнет конца, второй указатель окажется в желаемой позиции для перемещения хвоста к голове.

def move_tail_to_head(head):
    if not head or not head.next:
        return head
    slow = head
    fast = head
    prev = None
    while fast and fast.next:
        prev = slow
        slow = slow.next
        fast = fast.next.next
    prev.next = None
    fast.next = head
    return fast

Временная сложность: O(n), где n — количество узлов в связанном списке.

Метод 3: рекурсивный подход
Мы также можем решить эту проблему, используя рекурсивную функцию. Функция рекурсивно переместит хвост в начало подсписка, начиная со второго узла, а затем соответствующим образом обновит указатели.

def move_tail_to_head(head):
    if not head or not head.next:
        return head
    def helper(node):
        if not node.next:
            return node
        new_head = helper(node.next)
        node.next.next = node
        node.next = None
        return new_head
    return helper(head)

Временная сложность: O(n), где n — количество узлов в связанном списке.

В этой статье мы рассмотрели различные способы перемещения хвоста связанного списка в его начало. Мы обсудили наивный подход, эффективный подход с использованием двух указателей и рекурсивный подход. Каждый метод предлагает свой взгляд на решение проблемы. В зависимости от конкретных требований и ограничений вашего приложения вы можете выбрать наиболее подходящий метод.

Не забудьте проанализировать временную и пространственную сложность каждого метода, чтобы принять обоснованное решение. Приятного кодирования!