給定一個鏈結串列的頭節點
head和一個整數k，交換從頭數第k個和從尾數第k個節點的值，回傳修改後的串列。
Example:
Input: head = [1,2,3,4,5], k = 2 Output: [1,4,3,2,5]
Intuition
TIP
核心思路：用雙指針法找到從頭第 k 個和從尾第 k 個節點，然後交換值。
- 從頭第 k 個很好找，但從尾第 k 個需要技巧
- 可以用兩次遍歷（先算長度）或雙指針法（類似移除倒數第 N 個節點）
- 只交換值即可，不需要實際重新接指針
Approaches
1. Two Pass (Count Length) — O(n) / O(1)
- Idea: 先遍歷計算長度 n，從頭第 k 個是第 k 個，從尾第 k 個是第 n-k+1 個
- Time:
O(n) - Space:
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) — O(n) / O(1)
- Idea: 先讓指針走 k 步找到第一個節點，再用雙指針法同時走到尾端找到第二個節點
- Time:
O(n) - Space:
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 相同
- Key trick: 交換值比交換節點簡單得多，題目也只要求交換值