力扣 hot100 Day32

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

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

//自己写的
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* cur = head;int len=0;while(cur!=nullptr) {len++;cur = cur->next;}int tmp=0;if(tmp==len-n) {head = head->next;}cur=head;while(cur!=nullptr) {tmp++;if(tmp==len-n) {cur->next=cur->next->next;}cur = cur->next;}return head;        }
};

这里先遍历记录长度，然后找到倒数第n位进行删除

//抄的
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummy = new ListNode(0); // 虚拟头节点dummy->next = head;ListNode* fast = dummy;ListNode* slow = dummy;for (int i = 0; i <= n; i++) { // fast 先走 n+1 步fast = fast->next;}while (fast != nullptr) { // fast 和 slow 一起走fast = fast->next;slow = slow->next;}ListNode* toDelete = slow->next;slow->next = slow->next->next;delete toDelete;ListNode* newHead = dummy->next;delete dummy; // 释放虚拟头节点return newHead;}
};

居然没想到，双指针，快指针领先n步，即可找到倒数n位节点。

其实和上面也差不多，都是一个指针走到头，一个指针走到倒数第n位，但是并行处理了，只需一次遍历，效率更高。