解题思路

1. 双指针法：

   • 先让快指针 (fast) 先移动 n 步，这样当快指针到达链表尾部时，慢指针 (slow) 就恰好指向待删除节点的前一个节点。
   • 然后，同时移动 slow 和 fast，直到 fast 到达链表末尾。
   • 这时，slow.next 指向要删除的节点，直接修改 slow.next 跳过该节点，完成删除。

2. 特殊情况处理：

   • 如果 n == sz，说明要删除头节点，直接返回 head.next。
   • 如果删除后链表为空，要确保输出格式正确。

时间复杂度 & 空间复杂度

• 时间复杂度：O(sz)，仅遍历链表一次。
• 空间复杂度：O(1)，仅使用了几个指针变量，没有额外空间开销。

Python 代码

import sys

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def remove_nth_from_end(head, n):
    """ 删除链表的倒数第 n 个节点 """
    dummy = ListNode(-1)  # 创建虚拟头节点，方便处理删除头节点情况
    dummy.next = head
    fast = slow = dummy  # 初始化快慢指针

    # 让快指针先移动 n+1 步（确保 slow 最终停在待删除节点的前一个位置）
    for _ in range(n + 1):
        fast = fast.next

    # 同时移动快慢指针，直到 fast 到达链表末尾
    while fast:
        fast = fast.next
        slow = slow.next

    # 跳过要删除的节点
    slow.next = slow.next.next

    return dummy.next  # 返回新的链表头部

def build_linked_list(lst):
    """ 通过列表构建链表 """
    if not lst:
        return None
    head = ListNode(lst[0])
    current = head
    for val in lst[1:]:
        current.next = ListNode(val)
        current = current.next
    return head

def linked_list_to_list(head):
    """ 将链表转换为列表 """
    result = []
    while head:
        result.append(head.val)
        head = head.next
    return result

# 读取输入
sz = int(sys.stdin.readline().strip())  # 读取链表长度
lst = list(map(int, sys.stdin.readline().split())) if sz > 0 else []  # 读取链表数据
n = int(sys.stdin.readline().strip())  # 读取 n

# 处理链表删除操作
head = build_linked_list(lst)  # 构建链表
new_head = remove_nth_from_end(head, n)  # 删除倒数第 n 个节点
result = linked_list_to_list(new_head)  # 转换为列表

# 输出结果
print(" ".join(map(str, result))) if result else print()

Java 代码

import java.util.*;

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int sz = scanner.nextInt(); // 读取链表长度
        ListNode head = (sz > 0) ? buildLinkedList(scanner, sz) : null; // 构建链表
        int n = scanner.nextInt(); // 读取 n

        head = removeNthFromEnd(head, n); // 删除倒数第 n 个节点

        printLinkedList(head); // 输出结果
        scanner.close();
    }

    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1); // 创建虚拟头节点
        dummy.next = head;
        ListNode fast = dummy, slow = dummy;

        // 让快指针先移动 n+1 步
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }

        // 同时移动快慢指针，直到 fast 到达链表末尾
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // 跳过要删除的节点
        slow.next = slow.next.next;

        return dummy.next; // 返回新的链表头部
    }

    public static ListNode buildLinkedList(Scanner scanner, int sz) {
        ListNode head = new ListNode(scanner.nextInt());
        ListNode current = head;
        for (int i = 1; i < sz; i++) {
            current.next = new ListNode(scanner.nextInt());
            current = current.next;
        }
        return head;
    }

    public static void printLinkedList(ListNode head) {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val);
            if (current.next != null) System.out.print(" ");
            current = current.next;
        }
        System.out.println();
    }
}

C++ 代码

#include <iostream>
#include <vector>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode dummy(-1); // 创建虚拟头节点
    dummy.next = head;
    ListNode* fast = &dummy, * slow = &dummy;

    // 让快指针先移动 n+1 步
    for (int i = 0; i <= n; i++) {
        fast = fast->next;
    }

    // 同时移动快慢指针，直到 fast 到达链表末尾
    while (fast) {
        fast = fast->next;
        slow = slow->next;
    }

    // 跳过要删除的节点
    slow->next = slow->next->next;

    return dummy.next; // 返回新的链表头部
}

ListNode* buildLinkedList(vector<int>& lst) {
    if (lst.empty()) return nullptr;
    ListNode* head = new ListNode(lst[0]);
    ListNode* current = head;
    for (size_t i = 1; i < lst.size(); i++) {
        current->next = new ListNode(lst[i]);
        current = current->next;
    }
    return head;
}

void printLinkedList(ListNode* head) {
    while (head) {
        cout << head->val;
        if (head->next) cout << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    int sz;
    cin >> sz; // 读取链表长度

    vector<int> lst(sz);
    for (int i = 0; i < sz; i++) {
        cin >> lst[i];
    }

    int n;
    cin >> n; // 读取 n

    ListNode* head = buildLinkedList(lst);
    head = removeNthFromEnd(head, n);
    printLinkedList(head);

    return 0;
}

Leetcode 29.删除链表的倒数第N个结点-原题链接

题目描述

给定一个链表，删除链表的倒数第 n 个节点，并返回删除后的链表头节点。

输入描述

• 第一行输入一个整数 sz（$1 \leq sz \leq 30$），表示链表的长度。
• 第二行输入 sz 个整数（$0 \leq Node.val \leq 100$），表示链表的元素，按顺序存储。
• 第三行输入一个整数 n（$1 \leq n \leq sz$），表示要删除的倒数第 n 个节点。

输出描述

• 输出一行，表示删除后的链表，用空格分隔节点值。
• 如果链表为空，则直接输出一个空行。

样例输入 1

5
1 2 3 4 5
2

样例输出 1

1 2 3 5

样例输入 2

1
1
1

样例输出 2

样例输入 3

2
1 2
1

样例输出 3

1