Обратить однонаправленный связный список Golang
Чтобы обратить (реверсировать) односвязный список в Go, нужно поменять местами ссылки next между узлами, чтобы они указывали на предыдущий элемент, а не на следующий. При этом голова списка (head) после обращения будет указывать на последний элемент исходного списка.
Реализация функции для обращения списка
Допустим, у нас уже есть структура LinkedList и метод Print, как в предыдущем примере. Мы добавим к этой структуре метод Reverse, который будет обращать порядок узлов в списке.
Вот как это можно реализовать:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
package main import "fmt" // Node представляет элемент односвязного списка type Node struct { value int next *Node } // LinkedList представляет сам список, храня ссылку на первый элемент (голову) type LinkedList struct { head *Node } // Add добавляет новый элемент в конец списка func (list *LinkedList) Add(value int) { newNode := &Node{value: value} if list.head == nil { list.head = newNode return } current := list.head for current.next != nil { current = current.next } current.next = newNode } // Reverse обращает порядок элементов в списке func (list *LinkedList) Reverse() { var prev *Node current := list.head for current != nil { next := current.next // Запоминаем следующий узел current.next = prev // Перенаправляем текущую ссылку на предыдущий узел prev = current // Сдвигаем prev на текущий узел current = next // Переходим к следующему узлу } list.head = prev // Устанавливаем новую голову списка } // Print выводит элементы списка func (list *LinkedList) Print() { current := list.head for current != nil { fmt.Printf("%d -> ", current.value) current = current.next } fmt.Println("nil") } func main() { list := &LinkedList{} // Добавляем элементы list.Add(1) list.Add(2) list.Add(3) list.Add(4) fmt.Println("Исходный список:") list.Print() // 1 -> 2 -> 3 -> 4 -> nil // Обращаем порядок элементов list.Reverse() fmt.Println("Обращённый список:") list.Print() // 4 -> 3 -> 2 -> 1 -> nil } |
Объяснение работы метода Reverse
- Инициализация указателей: создаём указатели
prev(предыдущий узел) иcurrent(текущий узел). Изначальноprevуказывает наnil, аcurrent— на голову списка. - Перебор узлов: для каждого узла выполняем:
- Сохраняем указатель на следующий узел (
next). - Меняем ссылку
nextтекущего узла на предыдущий узел (prev), тем самым обращая направление. - Обновляем
prevиcurrent, чтобы перейти к следующему узлу.
- Сохраняем указатель на следующий узел (
- Установка новой головы: когда
currentстанетnil, последний обработанный узел (prev) станет новой головой списка.
Пример работы
- Исходный список:
1 -> 2 -> 3 -> 4 -> nil. - Обращённый список после вызова
Reverse:4 -> 3 -> 2 -> 1 -> nil.
Этот метод работает за линейное время O(n)O(n), так как мы проходим по каждому узлу один раз.
Recommended Posts
Golang map и Swiss Table
16.03.2025