Алгосы от Влада, часть 6. Инвертирование связанного списка на месте

• Введение
• Скользящее окно
• Два указателя или итератор
• Быстрый и медленный указатель
• Мерж интервалов
• Циклическая сортировка
• Инвертирование связанного списка на месте
• Дерево BFS
• Дерево DFS
• Две кучи
• Подмножества
• Модифицированный бинарный поиск
• Побитовый XOR
• Лучшие элементы К (top K elements)
• k-образный алгоритм слияния (K-Way merge)
• 0 or 1 Knapsack (Динамическое программирование)
• Топологическая сортировка

Введение

Во многих задачах нас просят инвертировать связи между некоторым набором узлов связанного списка. Часто требуется сделать это на месте, то есть использовать существующие объекты узлов и не выделять дополнительную память.

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

Давайте перейдём к первой задаче, чтобы разобраться, как работает этот паттерн.

Инвертирование всего связанного списка (простой уровень)

Условие задачи

Дана голова односвязного списка. Инвертируйте связанный список. Напишите функцию, которая возвращает новую голову инвертированного списка.

Решение

Чтобы инвертировать связанный список, нужно разворачивать по одному узлу за раз. Начнём с переменной current, которая изначально указывает на голову списка, и переменной previous, которая указывает на предыдущий уже обработанный узел. Изначально previous указывает на nil.

На каждом шаге мы инвертируем текущий узел, направляя его ссылку на previous, а затем переходим к следующему узлу. Также мы обновляем previous, чтобы эта переменная всегда указывала на предыдущий обработанный узел. Ниже показана работа алгоритма:

Код

Вот как будет выглядеть наш алгоритм:

package main

import "fmt"

type ListNode struct {
	Value int
	Next  *ListNode
}

func reverse(head *ListNode) *ListNode {
	current := head
	var previous *ListNode

	for current != nil {
		next := current.Next
		current.Next = previous
		previous = current
		current = next
	}

	return previous
}

func newList(values ...int) *ListNode {
	dummy := &ListNode{}
	current := dummy

	for _, value := range values {
		current.Next = &ListNode{Value: value}
		current = current.Next
	}

	return dummy.Next
}

func printList(head *ListNode) {
	first := true
	for current := head; current != nil; current = current.Next {
		if !first {
			fmt.Print(" ")
		}
		fmt.Print(current.Value)
		first = false
	}
	fmt.Println()
}

func main() {
	head := newList(2, 4, 6, 8, 10)
	head = reverse(head)

	fmt.Print("Узлы инвертированного связанного списка: ")
	printList(head)
}

Вывод:

Узлы инвертированного связанного списка: 10 8 6 4 2

Временная сложность

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

Пространственная сложность

Мы использовали только постоянный объём памяти, поэтому пространственная сложность алгоритма равна \(O(1)\).

Задачи главы

1. Инвертирование всего связанного списка (простой уровень)
2. Инвертирование участка связанного списка (средний уровень)
3. Инвертирование списка группами по k элементов (средний уровень)
4. Инвертирование каждой второй группы из k элементов (средний уровень)
5. Циклический сдвиг связанного списка вправо (средний уровень)

Похожие задания

Pattern: In-place Reversal of a LinkedList

1. Reverse a LinkedList (easy) Leetcode
2. Reverse a Sub-list (medium) Leetcode
3. Reverse every K-element Sub-list (medium) Leetcode
4. Reverse alternating K-element Sub-list (medium) GeeksforGeeks
5. Rotate a LinkedList (medium) Leetcode
6. Swap Nodes in Pairs (medium) Leetcode
7. Reverse Nodes in Even Length Groups (medium) Leetcode
8. Reorder List (medium) Leetcode