DEV Community 👩‍💻👨‍💻

Ivan
Ivan

Posted on

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

Давайте разберем задачу обмена элементов в связном списке. Ее можно найти по ссылке 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
Enter fullscreen mode Exit fullscreen mode

2) Далее надо найти k-ый элемент с начала списка. Для этого проитерируемся k раз.

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

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--
}
Enter fullscreen mode Exit fullscreen mode

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

while(fast != null && fast.next != null) {
    fast = fast.next
    slow = slow!!.next
}
Enter fullscreen mode Exit fullscreen mode

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

left?.`val` = slow?.`val`.also { slow?.`val` = left?.`val` }
Enter fullscreen mode Exit fullscreen mode

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

  • Оценка по времени 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
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)

Hi!I'm Noah!

Hey, my name is Noah and I’m the one who set up this ad!


My job is to get you to join DEV, so if you fancy doing me a favor, I’d love for you to create an account.
 
If you found DEV from searching around, here are a couple of our most popular articles on DEV: