Обмен элементов в связном списке

Давайте разберем задачу обмена элементов в связном списке. Ее можно найти по ссылке Swapping Nodes in a Linked List

Постановка задачи

Дана вершина связного списка head и целое число k.

Необходимо вернуть первый элемент связного списка после обмена k-го элемента от начала списка с k-м элементом с конца списка.

Примеры входных данных

Пример 1

Входные данные:
head = [1, 2, 3, 4, 5], k = 2
Результат:
[1, 4, 3, 2, 5]

Пример 2

Входные данные:
head = [7, 9, 6, 6, 7, 8, 3, 0, 9, 5], k = 5
Результат:
[7, 9, 6, 6, 8, 7, 3, 0, 9, 5]

Решение

Эта задача состоит из двух взаимосвязанных подзадач.

Первая подзадача заключается в определении k-го элемента с конца связного списка. Для решения этой задачи мы применим метод двух указателей. Вначале, быстрый указатель перемещается на k позиций вперед от начала списка. Затем оба указателя - быстрый и медленный - будут итерироваться синхронно по списку, сохраняя постоянную дистанцию в k элементов между собой. Когда быстрый указатель достигнет конца списка (указывая на null), медленный указатель будет указывать на k-й элемент с конца списка.

Вторая подзадача связана с обменом значений двух узлов в связном списке. Несмотря на свою относительную простоту, реализация этой задачи может варьироваться в зависимости от языка программирования. В случае с Kotlin, мы можем использовать функцию also для выполнения обмена значений между двумя узлами. Эта функция позволяет эффективно и безопасно обмениваться значениями между двумя объектами, минимизируя риск ошибок при переназначении значений.

Решение по шагам

1) Прежде всего, следует проверить, является ли первый узел связного списка пустым (равным null). Если это условие выполняется, нет необходимости в дальнейших вычислениях, и можно сразу вернуть null, так как список пуст, и выполнение алгоритма на нем не имеет смысла.

if (head == null) return null

2) После проверки первой вершины списка, следующим шагом будет определение k-го элемента с начала списка. Для этого необходимо выполнить итерацию k раз, двигаясь по списку.

var left: ListNode? = head
var index = k - 1
while(index != 0 && left != null) {
    left = left.next
    index--
}

3) После определения k-го элемента с начала списка, следующим шагом будет нахождение k-го элемента с конца списка. Для этого воспользуемся двумя указателями: медленным (slow) и быстрым (fast).

var slow: ListNode? = head
var fast: ListNode? = head
index = k - 1
while(index != 0 && fast != null) {
    fast = fast.next
    index--
}

Затем итерируем одновременно быстрый и медленный указатели.

while(fast != null && fast.next != null) {
    fast = fast.next
    slow = slow!!.next
}

4) В заключение, чтобы обменять значения левого и правого элементов местами, воспользуемся функцией also, доступной в языке программирования Kotlin. Эта функция позволяет эффективно и безопасно обмениваться значениями между двумя объектами, минимизируя риск ошибок при переназначении значений. Используя also, можно легко менять значения узлов между собой, завершая решение задачи.

left?.`val` = slow?.`val`.also { slow?.`val` = left?.`val` }

Оценка сложности

• Оценка временной сложности: O(n). Алгоритм имеет линейную временную сложность, так как мы проходимся по всем элементам списка только один раз. В процессе работы алгоритма два указателя перемещаются вдоль списка, что гарантирует линейное время выполнения.
• Оценка сложности по памяти: O(1). Алгоритм обладает постоянной сложностью по памяти, поскольку использует только четыре переменные (два указателя и две дополнительные переменные для хранения текущих значений левого и правого элементов). Объем используемой памяти не зависит от размера входного списка, что делает алгоритм эффективным с точки зрения расхода памяти.

Полное решение

fun swapNodes(head: ListNode?, k: Int): ListNode? {
    if (head == null) return null

    var left: ListNode? = head
    var index = k - 1
    while(index != 0 && left != null) {
        left = left.next
        index--
    }

    var slow: ListNode? = head
    var fast: ListNode? = head
    index = k - 1
    while(index != 0 && fast != null) {
        fast = fast.next
        index--
    }

    while(fast != null && fast.next != null) {
        fast = fast.next
        slow = slow!!.next
    }

    left?.`val` = slow?.`val`.also { slow?.`val` = left?.`val` }

    return head
}