给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1
输出：[]
示例 3：
输入：head = [1,2], n = 1
输出：[1]
提示：
链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
进阶：你能尝试使用一趟扫描实现吗？
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
暴力破解法
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode() : val(0), next(nullptr) {} 7 * ListNode(int x) : val(x), next(nullptr) {} 8 * ListNode(int x, ListNode *next) : val(x), next(next) {} 9 * }; 10 */ 11 class Solution { 12 public: 13 ListNode* removeNthFromEnd(ListNode* head, int n) { 14 ListNode *index=head; 15 ListNode* pre; 16 int i=0; 17 while(index) 18 { 19 index=index->next; 20 i++; 21 } 22 if(i<=1) 23 { 24 return NULL; 25 } 26 index=head; 27 i-=n; 28 if(i==0) 29 { 30 head=head->next; 31 return head; 32 } 33 for(int j=0;j<i;j++) 34 { 35 pre=index; 36 index=index->next; 37 } 38 pre->next=index->next; 39 return head; 40 } 41 };
进阶：
使用双指针法，即快慢指针。快指针先走 n 步，然后快慢指针同时走，直到快指针到达链表尾部。此时，慢指针指向的结点就是要删除的结点的前一个结点。然后我们可以修改慢指针的 next 指针，跳过要删除的结点，从而完成删除操作。
class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { // 创建一个虚拟头结点，方便处理边界情况 ListNode* dummy = new ListNode(0, head); // 初始化快慢指针 ListNode* fast = dummy; ListNode* slow = dummy; // 快指针先走 n 步 for (int i = 0; i < n; i++) { fast = fast->next; } // 快慢指针同时走，直到快指针到达尾部 while (fast->next != nullptr) { fast = fast->next; slow = slow->next; } // 删除慢指针的下一个结点 slow->next = slow->next->next; // 返回头结点 return dummy->next; } };