双指针法：删除链表的倒数第 n 个节点，并且返回链表的头结点

//链表算法：
//题目：
//给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
//
//问题函数定义：
//
//cpp
//ListNode* removeNthFromEnd(ListNode* head, int n);
//裁判测试程序样例：
//
//cpp
#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};
ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* dummy = new ListNode(0); // 使用哑节点简化边界情况处理
    dummy->next = head;

    ListNode* low = dummy;
    ListNode* fast = dummy;

    // fast指针先走 n+1 步
    for (int i = 0; i < n + 1; ++i) {
        if (!fast) return head; // 处理链表长度小于 n 的情况
        fast = fast->next;
    }

    // 同时移动 low 和 fast 指针，直到 fast 到达链表尾部
    while (fast) {
        low = low->next;
        fast = fast->next;
    }

    // 删除倒数第 n 个节点
    ListNode* temp = low->next;
    low->next = low->next->next;
    delete temp;

    ListNode* result = dummy->next;
    delete dummy;
    return result;
}

void printList(ListNode* head) {
    ListNode* curr = head;
    while (curr != NULL) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    cout << endl;
}

int main() {
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);

    int n = 2;
    cout << "Original list: ";
    printList(head);

    ListNode* new_head = removeNthFromEnd(head, n);

    cout << "List after removing " << n << "th node from end: ";
    printList(new_head);

    return 0;
}
//输入样例：
//
//链表：1 -> 2 -> 3 -> 4 -> 5
//n = 2
//输出样例：
//
//删除倒数第2个节点后的链表：1 -> 2 -> 3 -> 5