力扣 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]

思路

使用双指针方法，遍历一词链表就可以完成任务

1. 定义两个指针fast和slow都指向头节点。
2. 先让fast指针移动n+1次，这样fast和slow之间就有n+1个节点的间隔。
3. 然后同时移动fast和slow指针，直到fast指向链表的最后一个节点。这时，slow指针将指向要删除节点的前一个节点。
4. 修改slow的next指针，让其跳过下一个节点（即要删除的节点）。
5. 返回链表的头节点。

完整代码

#include<iostream>
#include<vector>
using namespace std;struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(nullptr) {}
};class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode dummyHead(0);dummyHead.next = head;ListNode *fast = &dummyHead;ListNode *slow = &dummyHead;while(n-- && fast->next != nullptr){fast = fast->next; }fast = fast->next; // 再向前移动一位while(fast != nullptr){fast = fast->next;slow = slow->next;}slow->next = slow->next->next;return dummyHead.next;}
};int main()
{Solution s;ListNode *head = new ListNode(1); // 创建一个新的链表节点，节点的值为1ListNode *current = head; // 创建指针指向链表头节点vector<int> values = {2, 3, 4, 5};for (int value : values) {current->next = new ListNode(value);current = current->next;}head = s.removeNthFromEnd(head, 2);// 打印删除节点后的链表current = head;while(current != nullptr){cout << current->val << " ";current = current->next;}return 0;
}