1721. Swapping Nodes in a Linked List

Medium

Description

給定一個鏈結串列的頭節點 head 和一個整數 k，交換從頭數第 k 個和從尾數第 k 個節點的值，回傳修改後的串列。

Example:

Input: head = [1,2,3,4,5], k = 2 Output: [1,4,3,2,5]

Intuition#

核心思路：用雙指針法找到從頭第 k 個和從尾第 k 個節點，然後交換值。

從頭第 k 個很好找，但從尾第 k 個需要技巧
可以用兩次遍歷（先算長度）或雙指針法（類似移除倒數第 N 個節點）
只交換值即可，不需要實際重新接指針

Approaches#

1: Two Pass (Count Length)#

概念: 先遍歷計算長度 n，從頭第 k 個是第 k 個，從尾第 k 個是第 n-k+1 個
時間複雜度: O(n)
空間複雜度: O(1)

class Solution {
    fun swapNodes(head: ListNode?, k: Int): ListNode? {
        var length = 0
        var curr = head
        while (curr != null) {
            length++
            curr = curr.next
        }

        var first = head
        for (i in 1 until k) {
            first = first?.next
        }

        var second = head
        for (i in 1 until length - k + 1) {
            second = second?.next
        }

        val temp = first!!.`val`
        first.`val` = second!!.`val`
        second.`val` = temp

        return head
    }
}

⭐2: Two Pointers (One Pass)#

概念: 先讓指針走 k 步找到第一個節點，再用雙指針法同時走到尾端找到第二個節點
時間複雜度: O(n)
空間複雜度: O(1)

class Solution {
    fun swapNodes(head: ListNode?, k: Int): ListNode? {
        var fast = head

        // 找到從頭第 k 個節點
        for (i in 1 until k) {
            fast = fast?.next
        }
        val first = fast

        // 雙指針找從尾第 k 個節點
        var slow = head
        while (fast?.next != null) {
            slow = slow?.next
            fast = fast.next
        }
        val second = slow

        // 交換值
        val temp = first!!.`val`
        first.`val` = second!!.`val`
        second.`val` = temp

        return head
    }
}

🔑 Takeaways#

Pattern: 找鏈結串列倒數第 k 個節點的雙指針技巧，與 LC 19 相同
關鍵技巧: 交換值比交換節點簡單得多，題目也只要求交換值