10. One-Pass Removal of k-th Node from End

Origin: One-Pass Removal of k-th Node from End

Given the head of a singly linked list and an integer k, remove the k-th node from the end in one traversal and return the new head. If k is invalid, return the original list.

Example

Input

head = [5, 6, 7, 8]
k = 3

Output

[6, 7, 8]

Explanation

The list has 4 nodes. 
The k-th node from the end with k=3 is the 4th node from the end (value 5), which is the head. Removing it yields [6,7,8].

Input Format

• The first line contains an integer n denoting the length of linked list.
• The next n lines contains elements of the linked list.
• The last line contains k.

Example

4
5
6
7
8
3

here 4 is the length of the linked list, followed by the elements of the list and value of k.

Constraints

• 0 <= number of nodes in head <= 1000
• -10^9 <= value of each node <= 10
• 0 <= k <= 10

Output Format

• Return the head of the modified linked list after removal.

Sample Input 0

1
5
1

Sample Output 0

5

Sample Input 1

2
1 
2
0

Sample Output 1

1

Resolution

我的解法（有 Bug）

function removeKthNodeFromEnd(head: SinglyLinkedListNode, k: number): SinglyLinkedListNode | {} {
    // Write your code here
    let cur: SinglyLinkedListNode | undefined = head
    const store: SinglyLinkedListNode[] = []
    while (cur) {
        store.push(cur)
        cur = cur.next
    }
    if (k <= store.length - 1) {
        if (k <= store.length - 2) {
            const preNode = store[store.length - 2 - k]
            const nextNode = store[store.length - k]
            preNode.next = nextNode
            console.log('k <= store.length - 2', k)
            return preNode
        } else {
            let toRemove = store[store.length - 1 - k]
            console.log('k > store.length - 2', k)
            return toRemove.next || {}
        }
    } else {
        console.log('k > store.length - 1', k)
        return head
    }
}

错误分析

错误一：返回值错了

删除中间节点时，代码 return preNode。但 preNode 是被删节点的前一个节点，不是链表头。应该返回 head（除非删的是头节点）。

举例：[5, 6, 7, 8]，k=1（删倒数第 2 个，即 7）。

• 代码返回 preNode（值为 6 的节点），但正确返回应该是 head（值为 5 的节点）。
• 虽然 5→6→8 链表结构是对的，但返回了 6 而不是 5，输出变成 [6, 8] 而不是 [5, 6, 8]。

注意：k 的语义没有错。 这道题的 k 是从 0 开始的偏移量：k=0 删最后一个，k=1 删倒数第 2 个，k=n-1 删 head。验证：head=[5,6,7,8]，k=3 删 5（倒数第 4 个），返回 [6,7,8]，和题目示例一致。

错误二：不是 one-pass

题目要求 one traversal（一次遍历），代码把所有节点存进数组 store，虽然只遍历了一次链表，但用了 O(n) 额外空间。题目标题叫 “One-Pass”，面试官会追问”能不能不用数组”。

正确解法：快慢指针

两个指针，fast 先走 k+1 步，然后 fast 和 slow 一起走，fast 到 null 时 slow 恰好停在被删节点的前一个。删头节点时没有前驱，用 dummy 节点解决。

function removeKthNodeFromEnd(head: SinglyLinkedListNode, k: number): SinglyLinkedListNode | null {
    if (!head || k <= 0) return head
 
    const dummy: SinglyLinkedListNode = { data: 0, next: head }
    let fast: SinglyLinkedListNode = dummy
    let slow: SinglyLinkedListNode = dummy
 
    // fast 先走 k+1 步，拉开间距
    for (let i = 0; i <= k; i++) {
        if (!fast) return head  // k 超出链表长度，无效
        fast = fast.next
    }
 
    // fast 和 slow 一起走，fast.next 到 null 时 slow 在被删节点前一个
    while (fast.next) {
        fast = fast.next
        slow = slow.next
    }
 
    // 删除 slow.next
    slow.next = slow.next.next
    return dummy.next
}

为什么是 k+1 步不是 k 步？

fast 先走 k+1 步，拉开 k+1 的间距。然后 fast 和 slow 一起走，while (fast.next) 保证 fast 停在最后一个节点（不是 null），此时 slow 恰好停在被删节点的前一个。

为什么用 while (fast.next) 而不是 while (fast)？

如果用 while (fast)，fast 会走到 null 才停，slow 会多走一步，停在被删节点本身而不是前一个。用 while (fast.next) 让 fast 停在最后一个节点，slow 就正好停在被删节点的前一个。

验证（head=[5,6,7,8]，k=3 删 head）：

• fast 走 4 步到 8，fast.next 是 null，循环不执行
• slow 停在 dummy，slow.next = head.next 跳过 head ✓

为什么用 dummy？

删头节点时，head 没有前驱节点。如果 slow 直接从 head 开始，无法指向 head 的”前一个”。加一个 dummy 节点指向 head，slow 从 dummy 开始，删头节点时 slow 就是 dummy，dummy.next = head.next 直接跳过头节点。

复杂度：

• 时间：O(n)，一次遍历。
• 空间：O(1)，只用两个指针。

同类题：LeetCode 19. 删除链表的倒数第 N 个结点。经典面试题，高频考点。