05 删除链表的倒数第N个结点 链表

19. 删除链表的倒数第 N 个结点

中等

相关标签

相关企业

提示

给你一个链表，删除链表的倒数第 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

进阶：你能尝试使用一趟扫描实现吗？

---

//双指针
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummyHead = new ListNode(0);dummyHead->next = head;ListNode* fast = dummyHead;ListNode* slow = dummyHead;n = n+1;while(n-- && fast != NULL){fast = fast->next;}while(fast!=NULL){fast = fast->next;slow = slow->next;}//此时slow指向要删除的结点的前驱结点ListNode* tmp = slow->next;slow->next = slow->next->next;delete tmp;tmp = NULL;return dummyHead->next;}
};

• 普通思路：遍历一遍得出链表的总长度，然后将倒数第N个结点换算成正数第X个结点
• 双指针思路：让fast和slow都指向虚拟头结点，让fast先走N步时，fast指向NULL时slow就指向倒数第N个结点
• **由于想要删除倒数第N个结点，slow指向其前一个就行了，所以让fast先走N+1步骤 **