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 要求。但把所有节点存进数组 store，用了 O(n) 额外空间。快慢指针解法可以做到 O(1) 空间，面试官会追问”能不能不用数组”。

数组解法（修正版）

修正了返回值的 bug，其余逻辑不变：

function removeKthNodeFromEnd(head: SinglyLinkedListNode, k: number): SinglyLinkedListNode | null {
    if (!head || k < 0) return head
 
    const store: SinglyLinkedListNode[] = []
    let cur: SinglyLinkedListNode | null = head
    while (cur) {
        store.push(cur)
        cur = cur.next
    }
 
    // k 范围检查：0 <= k <= store.length - 1
    if (k > store.length - 1) return head
 
    // 删的是 head
    if (k === store.length - 1) {
        return head.next || null
    }
 
    // 删中间或尾部
    const preNode = store[store.length - 2 - k]
    preNode.next = preNode.next.next
    return head
}

复杂度：

• 时间：O(n)，一次遍历。
• 空间：O(n)，存储所有节点。

最优解法：快慢指针

fast 从 head 出发，先走 k 步拉开间距。然后 fast 和 slow 一起走，while(fast.next) 保证 fast 停在最后一个节点，此时 slow 恰好停在被删节点的前一个。

function removeKthNodeFromEnd(head: SinglyLinkedListNode, k: number): SinglyLinkedListNode | null {
    if (!head || k < 0) return head
 
    let fast: SinglyLinkedListNode = head
    const dummy: SinglyLinkedListNode = { data: 0, next: head }
    let slow: SinglyLinkedListNode = dummy
 
    // fast 先走 k 步，拉开间距
    for (let i = 0; i < k; i++) {
        if (fast.next) {
            fast = fast.next
        } else {
            return head  // k 越界
        }
    }
 
    // fast 和 slow 一起走，fast.next 到 null 时 slow 在被删节点前一个
    while (fast.next) {
        fast = fast.next
        slow = slow.next!
    }
 
    slow.next = slow.next?.next
    return dummy.next || null
}

为什么 fast 走 k 步而不是 k+1 步？

fast 从 head 出发走 k 步，slow 从 dummy 出发。两者的起点差一个节点（dummy 在 head 前面），所以走完之后 fast 和 slow 的间距是 k+1。while(fast.next) 走完后，slow 停在被删节点的前一个。

如果 fast 从 dummy 出发走 k+1 步，效果完全等价，但代码多一步不直观。

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

fast 停在最后一个节点时，fast.next 是 null，循环退出。此时 slow 正好在被删节点前一个。如果用 while(fast)，fast 会走到 null，slow 会多走一步，停在被删节点本身。

为什么用 dummy？

删头节点时，head 没有前驱节点。slow 从 dummy 开始，删 head 时 slow 就是 dummy，dummy.next = head.next 直接跳过 head。

复杂度：

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

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