来源：力扣 （LeetCode）
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
一、题目描述
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
例如：给定一个链表: 1->2->3->4->5, 和 n = 2 。当删除了倒数第二个节点后，链表变为 1->2->3->5 。
说明：
给定的 n 保证是有效的。
进阶：你能尝试使用一趟扫描实现吗？
二、题解
使用快慢指针，快指针先走 n 步，满指针再走，当快指针为空的时候满指针就是倒数第 n 个节点。
和 《剑指 offer 》面试题 22：链表中的倒数第 k 个节点类似，知识剑指 offer 中是返回倒数第 n 个节点，这道题目是删除倒数第 n 各节点，多了个删除操作。
三、代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
class Solution { public: ListNode *removeNthFromEnd(ListNode *head, int n) { ListNode *prev, *fast, *slow; prev = nullptr; fast = head; slow = head; // 快指针先走 n 步 while (fast && n--) fast = fast->next; // n 大于链表长度，直接返回 head if (!fast && n > 0) return head; // 遍历快慢指针，并备份慢指针 while (fast != nullptr) { prev = slow; fast = fast->next; slow = slow->next; } // 删除节点，注意删除的节点可能是链表收尾节点 if (prev) { // 如果删除的是最后一个节点，slow 为空 prev->next = slow ? slow->next : nullptr; return head; } else { // 删除的首节点，返回首节点的下一个节点 return head->next; } } }; |
