LeetCode Entry

1721. Swapping Nodes in a Linked List

15.05.2023 medium 2023 kotlin

Swap the values of the head-tail k'th ListNodes.

1721. Swapping Nodes in a Linked List medium blog post substack

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/213

Problem TLDR

Swap the values of the head-tail k’th ListNodes.

Intuition

As we aren’t asked to swap nodes, the problem is to find nodes.

Approach

Travel the fast pointer at k distance, then move both fast and two nodes until fast reaches the end.

Complexity

• Time complexity: \(O(n)\)
• Space complexity: \(O(1)\)

Code

fun swapNodes(head: ListNode?, k: Int): ListNode? {
    var fast = head
    for (i in 1..k - 1) fast = fast?.next
    val one = fast
    var two = head
    while (fast?.next != null) {
        two = two?.next
        fast = fast?.next
    }
    one?.`val` = two?.`val`.also { two?.`val` = one?.`val` }
    return head
}