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

Давайте разберем задачу обмена элементов в связном списке. Ее можно найти по ссылке 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-ый элемент с конца списка.
Вторая подзадача это обмен значений двух вершин. В целом она достаточно тривиальна, но в котлине мы ее решим с помощью функции 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-ый элемент с конца списка. Для этого используем медленный slow и быстрый fast указатели. Сначала итерируем k раз быстрый указатель.

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.

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
}