09 · УКАЗАТЕЛИ

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

Изменение связей, dummy-узел и fast/slow — три главных инструмента.

2 Go-примитива3 примераInterview 150

СНАЧАЛА ИНСТРУМЕНТЫ

Примитивы Go

Минимальный синтаксис, который понадобится в решении.

Узел

type ListNode struct {
    Val int
    Next *ListNode
}

nil завершает список; узлы изменяются через указатели.

Dummy

dummy := &ListNode{Next: head}
prev := dummy

Фиктивная голова унифицирует удаление первого и остальных узлов.

ПРАКТИКА

Примеры решений

Три идиоматичных решения на Go с оценкой времени и памяти.

ПРИМЕР РЕШЕНИЯ

Разворот списка

Перенаправляем Next по одному узлу.

O(n) time · O(1) space

solution.go

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    for head != nil {
        next := head.Next
        head.Next = prev
        prev, head = head, next
    }
    return prev
}

ПРИМЕР РЕШЕНИЯ

Поиск цикла

Быстрый указатель догоняет медленный внутри цикла.

O(n) time · O(1) space

solution.go

func hasCycle(head *ListNode) bool {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow, fast = slow.Next, fast.Next.Next
        if slow == fast { return true }
    }
    return false
}

ПРИМЕР РЕШЕНИЯ

Слияние двух списков

Dummy-узел собирает результат без отдельной обработки головы.

O(n + m) time · O(1) space

solution.go

func mergeTwoLists(a, b *ListNode) *ListNode {
    dummy := &ListNode{}
    tail := dummy
    for a != nil && b != nil {
        if a.Val < b.Val { tail.Next, a = a, a.Next } else { tail.Next, b = b, b.Next }
        tail = tail.Next
    }
    if a != nil { tail.Next = a } else { tail.Next = b }
    return dummy.Next
}

ПЕРЕД КОДОМ

Чек-лист рассуждения

Сохрани next до изменения связи
Проверь nil и один узел
Нарисуй три соседних узла