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

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

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

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

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

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

프라이머 1

Входные данные:
헤드 = [1, 2, 3, 4, 5], k = 2
결과:
[1, 4, 3, 2, 5]

예문 2

Входные данные:
헤드 = [7, 9, 6, 6, 7, 8, 3, 0, 9, 5], k = 5
결과:
[7, 9, 6, 6, 8, 7, 3, 0, 9, 5]

레슈니예

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

Решение по шаgamm

1) Сначала необходимо проверить первую вершину списка. Если она равна null , null .

if (head == null) return null

2) Далее надо найти k-ый элеmentент с начала списка. Для этого проитерируемся 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
}