删除链表的倒数第 N 个结点

• https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

描述

• 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2

输入：head = [1], n = 1
输出：[]

示例 3

输入：head = [1,2], n = 1
输出：[1]

提示

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz
• 进阶：你能尝试使用一趟扫描实现吗？

Typescript 版算法实现

1 ) 方案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 {
    // 创建一个虚拟头节点，简化边界情况处理
    const dummy = new ListNode(0, head);
    let length = getLength(head);
    let cur: ListNode | null = dummy;

    // 移动到要删除节点的前一个位置
    for (let i = 1; i < length - n + 1; ++i) {
        if (cur?.next) {
            cur = cur.next;
        } else {
            break;
        }
    }

    // 删除目标节点
    if (cur && cur.next) {
        cur.next = cur.next.next;
    }

    // 返回新的头节点
    return dummy.next;
}

function getLength(head: ListNode | null): number {
    let length = 0;
    while (head !== null) {
        ++length;
        head = head.next;
    }
    return length;
}

2 ) 方案2: 双while

/**
 * 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 {
  // let dummy = new ListNode(null,head)
  const dummy = {
    next:head
  }
  let slow = dummy
  let fast = dummy
  while(n--){
    fast = fast.next
  }
  while(fast.next){
    fast = fast.next
    slow = slow.next
  }
  slow.next = slow.next.next
  return dummy.next
};

3 ) 方案3：栈

/**
 * 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 {
    const nodes: ListNode[] = [];
    const dummy = new ListNode(0, head);
    let node: ListNode | null = dummy;

    // 收集所有节点到数组中
    while (node !== null) {
        nodes.push(node);
        node = node.next;
    }

    // 找到要删除节点的前一个节点
    const prev = nodes[nodes.length - 1 - n];

    // 删除目标节点
    if (prev.next !== null) {
        prev.next = prev.next.next;
    }

    // 返回新的头节点
    return dummy.next;
}

4 ) 方案4：双指针

/**
 * 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 {
    // 创建一个虚拟头节点，简化边界情况处理
    const dummy = new ListNode(0, head);
    let first: ListNode | null = head;
    let second: ListNode | null = dummy;

    // 移动 first 指针，使其领先 second 指针 n 步
    for (let i = 0; i < n && first !== null; ++i) {
        first = first.next;
    }

    // 同时移动 first 和 second 指针，直到 first 到达链表末尾
    while (first !== null) {
        first = first.next;
        if (second) second = second.next;
    }

    // 删除目标节点
    if (second && second.next) {
        second.next = second.next.next;
    }

    // 返回新的头节点
    return dummy.next;
}