题目描述

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

示例:

输入: 1->2->3->4->5, n = 2
输出: 1->2->3->5

解题思路

使用双指针的方法来找到倒数第 n 个节点，然后删除该节点。

解题步骤

1. 使用两个指针 fast 和 slow，初始时都指向链表的头节点。
2. 先将 fast 指针向前移动 n+1 步。
3. 然后，同时移动 fast 和 slow 指针，直到 fast 指针到达链表末尾。
4. 此时，slow 指针指向倒数第 n+1 个节点。
5. 将 slow 指针的下一个节点删除，即将 slow.next 指向 slow.next.next。
6. 返回头节点。

C#代码实现

public ListNode RemoveNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0);dummy.next = head;ListNode fast = dummy;ListNode slow = dummy;// 先将 fast 指针向前移动 n+1 步for (int i = 0; i <= n; i++) {fast = fast.next;}// 同时移动 fast 和 slow 指针，直到 fast 到达链表末尾while (fast != null) {fast = fast.next;slow = slow.next;}// 删除倒数第 n 个节点slow.next = slow.next.next;return dummy.next;
}

C代码实现

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {struct ListNode* dummy = malloc(sizeof(struct ListNode));dummy->next = head;struct ListNode* fast = dummy;struct ListNode* slow = dummy;// 先将 fast 指针向前移动 n+1 步for (int i = 0; i <= n; i++) {fast = fast->next;}// 同时移动 fast 和 slow 指针，直到 fast 到达链表末尾while (fast != NULL) {fast = fast->next;slow = slow->next;}// 删除倒数第 n 个节点struct ListNode* temp = slow->next;slow->next = slow->next->next;free(temp);return dummy->next;
}

时间复杂度和空间复杂度

• 时间复杂度：O(n)，其中 n 是链表的长度。两个指针分别遍历链表一次。
• 空间复杂度：O(1)。除了常数级别的变量，算法的空间复杂度是常数级别的。