删除链表倒数第N个结点（3种实现方案）

删除链表倒数第N个结点可通过遍历两次链表、双指针或递归实现，以下是具体方案：

• 核心思路：先遍历链表统计结点总数L，再找到第L-N个结点（即倒数第N+1个结点），修改其next指针。
• 步骤：

  添加头结点简化操作。

  第一次遍历统计链表长度L。

  若N+1>L，说明目标结点不存在，返回NULL。

  第二次遍历找到第L-N个结点。

  删除目标结点并释放内存。

• 代码示例：ListNode* removeNthFromEnd(ListNode* head, int N) { int length = 0; ListNode* temp = (ListNode*)malloc(sizeof(ListNode)); temp->next = head; head = temp; ListNode* current = temp; while (current != NULL) { length++; current = current->next; } if (N + 1 > length) return NULL; current = head; for (int i = 1; i < length - N; i++) { current = current->next; } ListNode* target = current->next; current->next = current->next->next; free(target); head = temp->next; free(temp); return head;}

• 核心思路：使用两个指针P1和P2，P1先移动N步，然后同时移动P1和P2，直到P1到达末尾，此时P2指向倒数第N+1个结点。
• 步骤：

  添加头结点。

  初始化P1和P2指向头结点。

  P1先移动N步。

  同时移动P1和P2，直到P1指向最后一个结点。

  修改P2的next指针，删除目标结点。

• 代码示例：ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* temp = (ListNode*)malloc(sizeof(ListNode)); temp->next = head; head = temp; ListNode* P1 = head; ListNode* P2 = head; for (int i = 0; i < n; i++) { if (P1 == NULL) break; P1 = P1->next; } if (P1 == NULL || P2 == NULL) return NULL; while (P1->next != NULL) { P1 = P1->next; P2 = P2->next; } ListNode* target = P2->next; P2->next = P2->next->next; free(target); head = temp->next; free(temp); return head;}

• 核心思路：递归统计结点数量，回溯时找到倒数第N+1个结点并删除目标结点。
• 步骤：

  添加头结点。

  递归统计结点数量，回溯时检查是否到达倒数第N+1个结点。

  删除目标结点并释放内存。

• 代码示例：int removeNthFromEndRecursive(ListNode* head, int n) { if (head == NULL) return 0; int count = removeNthFromEndRecursive(head->next, n) + 1; if (count == n + 1) { ListNode* temp = head->next; head->next = head->next->next; free(temp); } return count;}ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* temp = (ListNode*)malloc(sizeof(ListNode)); temp->next = head; head = temp; removeNthFromEndRecursive(head, n); head = temp->next; free(temp); return head;}

• 遍历两次链表：逻辑简单，但需两次遍历，效率较低。
• 双指针法：仅需一次遍历，效率最高，推荐使用。
• 递归法：代码简洁，但递归调用消耗栈内存，可能引发栈溢出。

• 添加头结点可简化删除首元结点的操作。
• 操作完成后需释放动态分配的内存，避免内存泄漏。
• 递归方案需注意递归深度，避免栈溢出。

以上方案均能有效删除链表倒数第N个结点，实际应用中可根据需求选择合适方案。