TypeScript算法-19. 删除链表的倒数第 N 个结点

思路

要删除倒数第N个节点，就要找到倒数第N+1个节点，然后直接将next指针指向next.next即可。

为了找到倒数第N+1个节点，可以使用快慢指针，让快指针先走n步，然后快慢指针同时往前走，直到快指针到链表尾部，这时候慢指针就刚好指在倒数第N+1个节点的位置。

要注意的是，有可能要删除的是链表第一个节点，所以我们要新建一个哨兵节点，使其指向链表头，然后快慢指针的起点都从哨兵节点开始。

代码

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
    if (head === null) return null;
    // 哨兵节点，指向链表头
    const res = new ListNode();
    res.next = head;
    let slow: ListNode | null, fast: ListNode | null;
    // 快慢指针都从哨兵节点起步
    slow = res;
    fast = res;
    let fastStep = n;
    // 快指针先走n步
    while (fastStep > 0) {
        fast = fast?.next!;  // 题目保证n的长度在链表范围内
        fastStep = fastStep - 1;
    }
    // 快慢指针同时走，直到fast指向链表尾
    while(fast.next !== null) {
        slow = slow?.next!;
        fast = fast?.next;
    }
    // 此时slow指针指向要删除的节点的上一个节点
    slow.next = slow.next?.next!;
    return res.next;
}

// 本地测试用的链表遍历函数
function traverseList(head: ListNode | null) {
    while(head !== null) {
        console.log(head.val, ', ');
        head = head.next;
    }
}

let testHead = new ListNode(1);
let removeNthFromEnd_testHead = removeNthFromEnd(testHead, 1);
traverseList(removeNthFromEnd_testHead);