Обмен элементов в связном списке
Tags: kotlin, algorithms, leetcode, medium
Published: 2022-09-12 06:55:18

Давайте разберем задачу обмена элементов в связном списке. Ее можно найти по ссылке [Swapping Nodes in a Linked List](https://leetcode.com/problems/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, так как список пуст, и выполнение алгоритма на нем не имеет смысла.

```kotlin
if (head == null) return null
```

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

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

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

```kotlin
var slow: ListNode? = head
var fast: ListNode? = head
index = k - 1
while(index != 0 && fast != null) {
    fast = fast.next
    index--
}
```
Затем итерируем одновременно быстрый и медленный указатели.

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

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

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

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

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

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

```kotlin
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
}
```