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

在数据结构与算法的世界中，链表是一种常见且重要的数据结构。而链表中倒数第 N 个结点的删除问题，是一个具有一定挑战性的操作。

让我们来理解一下这个问题。给定一个链表和一个整数 N，我们需要删除链表中倒数第 N 个结点。为了解决这个问题，我们可以使用双指针的方法。

我们设置两个指针，一个快指针和一个慢指针。快指针先向前移动 N 步，然后慢指针开始移动。当快指针到达链表末尾时，慢指针所指向的位置就是倒数第 N 个结点的前一个位置。

接下来，通过一些代码示例来更清晰地展示这个过程。以下是使用 C 语言实现的代码：

#include <stdio.h>
#include <stdlib.h>

// 链表节点结构体
typedef struct ListNode {
    int val;
    struct ListNode *next;
} ListNode;

// 创建新节点
ListNode* createNode(int val) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->val = val;
    newNode->next = NULL;
    return newNode;
}

// 删除倒数第 N 个节点
ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* fast = head;
    ListNode* slow = head;

    // 快指针先移动 N 步
    for (int i = 0; i < n; i++) {
        if (fast!= NULL) {
            fast = fast->next;
        } else {
            return head;
        }
    }

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

    // 删除倒数第 N 个节点
    if (slow == head && fast->next == NULL) {
        head = head->next;
    } else {
        ListNode* temp = slow->next;
        slow->next = slow->next->next;
        free(temp);
    }

    return head;
}

// 打印链表
void printList(ListNode* head) {
    ListNode* curr = head;
    while (curr!= NULL) {
        printf("%d ", curr->val);
        curr = curr->next;
    }
    printf("\n");
}

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

    int n = 2;

    printf("原始链表: ");
    printList(head);

    head = removeNthFromEnd(head, n);

    printf("删除倒数第 %d 个节点后的链表: ", n);
    printList(head);

    return 0;
}

这种方法的时间复杂度为 O(n)，空间复杂度为 O(1)，是一种比较高效的解决方案。

在实际应用中，链表倒数第 N 个结点的删除问题可能会出现在各种场景中，比如在处理动态数据、实现特定的逻辑流程等方面。熟练掌握这个问题的解决方法，对于提升我们的编程能力和解决实际问题的能力都具有重要意义。

通过巧妙地运用双指针的技巧，我们能够有效地解决链表倒数第 N 个结点的删除问题，为我们在数据结构和算法的领域中积累更多的经验和技巧。