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

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

**题目描述：**给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

**关键：**fast首先走n + 1步 ，为什么是n+1呢，因为只有这样同时移动的时候slow才能指向删除节点的上一个节点（方便做删除操作）

image-20240113171317370

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(head == nullptr) {
            return nullptr;
        }
        ListNode* dummyHead = new ListNode(-1, head);
        ListNode* fast = dummyHead;
        ListNode* slow = dummyHead;
        ++n;
        while(n--) {    //这里不要写成--n
            fast = fast->next;
        }
        while(fast) {
            fast = fast->next;
            slow = slow->next;
        }
        ListNode* temp = slow->next;
        slow->next = slow->next->next;
        delete temp;
        temp = dummyHead->next;
        delete dummyHead;
        dummyHead = nullptr;
        return temp;
    }
};

while()中--n和n--不一样

//借用2.6的代码

class Solution {
public:
	ListNode* findFromEnd(ListNode* list, int n) {
		ListNode* fast = list;
		ListNode* slow = list;
		while(fast && n--) {	//先走N步
			fast = fast->next;
		}
		while(fast) {	//当fast为空时 slow刚好指在目标元素上
			fast = fast->next;
			slow = slow->next;
		}
		return slow;
	}
	
    ListNode* removeNthFromEnd(ListNode* head, int n) {
  		ListNode* cur = findFromEnd(head, n + 1);	//因为删除元素需要知道前一个元素的位置
        ListNode* temp = cur->next;
        cur->next = cur->next->next;
        delete temp;
        temp = nullptr;
        return head;
    }
};