Связанные списки и стеки

206.

Reverse Linked List

Easy связный список указатели

Дан головной узел head односвязного списка. Разверните список и верните новый головной узел.

Ограничения: 0 ≤ количество узлов ≤ 5000. Задача есть в итеративной и рекурсивной версиях — попробуйте обе.

Пример 1

1 → 2 → 3 → 4 → 5
output: 5 → 4 → 3 → 2 → 1

Пример 2

head = null
output = null

Подсказка

Держите три указателя: prev, curr и nxt. Сначала сохраните curr.next, только потом разверните связь.

Решение

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

def reverse_list(head):                 # итеративно
    prev, curr = None, head
    while curr:
        nxt = curr.next                 # сохранить, пока не потеряли
        curr.next = prev                # развернуть связь
        prev, curr = curr, nxt          # шаг вперёд
    return prev

def reverse_list_rec(head):             # рекурсивно
    if not head or not head.next:
        return head
    new_head = reverse_list_rec(head.next)
    head.next.next = head               # разворот связи «назад по ходу»
    head.next = None
    return new_head

Сложность: время O(n), память O(1) в итеративной версии и O(n) в рекурсивной (стек вызовов).

141.

Дан головной узел списка. Верните true, если в списке есть цикл, иначе false. Цикл означает, что, двигаясь по next, можно вернуться в уже посещённый узел. Дополнительной памяти использовать нельзя.

Ограничения: 0 ≤ количество узлов ≤ 10⁴.

Пример 1

3 → 2 → 0 → -4
     ↑         |
     └─────────┘
output = true

Пример 2

1 → 2 → null
output = false

Подсказка

Множество посещённых узлов — это O(n) памяти. Вместо него пустите два указателя с разной скоростью: медленный шагает на 1, быстрый на 2. Внутри цикла они обязательно встретятся.

Решение

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

Сложность: время O(n), память O(1).

Продолжение темы — 142. Linked List Cycle II (Medium): найти узел, с которого цикл начинается.

232.

Implement Queue using Stacks

Easy стек очередь амортизация

Реализуйте очередь (FIFO), используя только два стека и стандартные операции стека: push, pop, peek, empty. Доступ к элементам иначе, чем через стек, запрещён.

Требования: push, pop, peek, empty; все операции в сумме должны быть эффективными (амортизированно O(1)).

Пример

push(1); push(2); peek() → 1; pop() → 1; empty() → false

Подсказка

Один стек — «входной», второй — «выходной». Периодически переливайте входной в выходной: два реверса дают нужный порядок FIFO.

Решение

class QueueViaStacks:
    def __init__(self):
        self.inbox, self.outbox = [], []

    def push(self, x):
        self.inbox.append(x)

    def _transfer(self):
        if not self.outbox:                      # переливаем только когда нужно
            while self.inbox:
                self.outbox.append(self.inbox.pop())

    def pop(self):
        self._transfer()
        return self.outbox.pop()

    def peek(self):
        self._transfer()
        return self.outbox[-1]

    def empty(self):
        return not self.inbox and not self.outbox

Сложность: push — O(1), pop/peek — O(1) амортизированно (каждый элемент переливается не более одного раза), память O(n).

—

Tower of Hanoi

Codewars рекурсия стеки

Есть три стержня. На первом снизу вверх стоят кольца в порядке убывания размера. Нужно перенести всю башню на другой стержень, перенося за один ход верхнее кольцо и никогда не кладя большее кольцо на меньшее. Верните список ходов в виде пар (откуда, куда).

Ограничения: число ходов растёт экспоненциально (2ⁿ − 1), поэтому на практике n невелико.

Пример

hanoi(3, 1, 3, 2)   # n=3, source=1, target=3, auxiliary=2
output = [(1, 3), (1, 2), (3, 2), (1, 3), (2, 1), (2, 3), (1, 3)]
# всего 2**3 - 1 = 7 ходов

Подсказка

Сведите задачу к меньшей: чтобы перенести n колец, сначала уберите верхние n − 1 на вспомогательный стержень, затем переложите самое большое кольцо, затем верните n − 1 колец сверху на целевой стержень.

Решение

def hanoi(n, source=1, target=3, auxiliary=2):
    if n == 0:
        return []
    moves = hanoi(n - 1, source, auxiliary, target)   # n-1 → вспомогательный
    moves.append((source, target))                    # самое большое кольцо
    moves += hanoi(n - 1, auxiliary, target, source)  # n-1 → целевой
    return moves

Сложность: время и объём вывода O(2ⁿ), глубина рекурсии O(n).

33.

Search in Rotated Sorted Array

Medium бинарный поиск массив

Дан массив различных чисел, отсортированный по возрастанию и повёрнутый на неизвестное число позиций (например [4,5,6,7,0,1,2]). Дан target — верните индекс элемента или -1, если элемента нет. Решение должно быть за O(log n).

Ограничения: 1 ≤ nums.length ≤ 5000, значения уникальны.

Пример 1

nums = [4, 5, 6, 7, 0, 1, 2], target = 0
output = 4

Пример 2

nums = [4, 5, 6, 7, 0, 1, 2], target = 3
output = -1

Подсказка

В точке mid левая или правая половина гарантированно отсортирована целиком. Определите, какая именно (сравнением nums[lo] и nums[mid]), и решайте, лежит ли target внутри этой «чистой» половины; если нет — ищите в другой.

Решение

def search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:                  # левая половина отсортирована
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                                      # отсортирована правая
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

Сложность: время O(log n), память O(1).