C语言算法-解答删除链表的倒数第 N 个结点问题的C语言实现

题目

给定一个链表，删除链表的倒数第 N 个结点，并返回链表的头结点。

引言

删除链表的倒数第 N 个结点问题需要注意边界条件和特殊情况的处理。我们可以使用双指针的方法来解决这个问题，其中一个指针先走 N 步，然后两个指针同时向前走，直到第一个指针到达链表末尾。这样，第二个指针指向的结点就是要删除的结点。解决这个问题需要对链表进行遍历和指针操作。

算法思路

我们将使用双指针的方法来解决删除链表的倒数第 N 个结点问题。

算法的步骤如下：

1. 创建一个虚拟头结点 dummy，并将其指向链表的头结点。这样可以方便处理删除头结点的情况。
2. 使用两个指针 fast 和 slow，初始化它们都指向虚拟头结点 dummy。
3. 让 fast 先向前移动 N+1 步，将两个指针之间相隔 N 个结点。
4. 同时移动 fast 和 slow，直到 fast 到达链表末尾。这样，slow 就指向要删除的结点的前一个结点。
5. 修改指针，将 slow 的下一个结点指向要删除的结点的下一个结点，实现删除操作。
6. 返回链表的头结点，即虚拟头结点 dummy 的下一个结点。

代码实现

下面是使用C语言实现的代码：

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

typedef struct ListNode {
    int val;
    struct ListNode* next;
} ListNode;

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* dummy = (ListNode*)malloc(sizeof(ListNode));
    dummy->next = head;

    ListNode* fast = dummy;
    ListNode* slow = dummy;

    for (int i = 0; i < n + 1; i++) {
        fast = fast->next;
    }

    while (fast != NULL) {
        fast = fast->next;
        slow = slow->next;
    }

    ListNode* toRemove = slow->next;
    slow->next = slow->next->next;
    free(toRemove);

    ListNode* result = dummy->next;
    free(dummy);

    return result;
}

void printList(ListNode* head) {
    ListNode* current = head;

    while (current != NULL) {
        printf("%d ", current->val);
        current = current->next;
    }

    printf("\n");
}

int main() {
    // 创建示例链表: 1 -> 2 -> 3 -> 4 -> 5
    ListNode* head = (ListNode*)malloc(sizeof(ListNode));
    head->val = 1;

    ListNode* node1 = (ListNode*)malloc(sizeof(ListNode));
    node1->val = 2;
    head->next = node1;

    ListNode* node2 = (ListNode*)malloc(sizeof(ListNode));
    node2->val = 3;
    node1->next = node2;

    ListNode* node3 = (ListNode*)malloc(sizeof(ListNode));
    node3->val = 4;
    node2->next = node3;

    ListNode* node4 = (ListNode*)malloc(sizeof(ListNode));
    node4->val = 5;
    node3->next = node4;
    node4->next = NULL;

    printf("Original List: ");
    printList(head);

    int n = 2;
    ListNode* result = removeNthFromEnd(head, n);

    printf("After Removal: ");
    printList(result);

    // 释放内存
    while (result != NULL) {
        ListNode* temp = result;
        result = result->next;
        free(temp);
    }

    return 0;
}

算法分析

该算法只需要对链表进行一次遍历，所以时间复杂度为 O(L)，其中 L 是链表的长度。

空间复杂度为 O(1)，算法只使用了常数级别的额外空间。

示例和测试

示例输入1:

链表: 1 -> 2 -> 3 -> 4 -> 5，n = 2

示例输出1:

删除倒数第二个结点后的链表: 1 -> 2 -> 3 -> 5

示例输入2:

链表: 1，n = 1

示例输出2:

删除倒数第一个结点后的链表: 空链表

示例输入3:

链表: 1 -> 2，n = 2

示例输出3:

删除倒数第二个结点后的链表: 2

总结

本文使用C语言实现了解答删除链表的倒数第 N 个结点问题的代码。通过使用双指针的方法，我们能够删除链表中倒数第 N 个结点，并返回删除后的链表。该算法的时间复杂度为 O(L)，空间复杂度为 O(1)。