目录

• 题目
• • 1.链接
  • 2.题目描述
  • 3.解题思路
  • 4.题解

题目

1.链接

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

2.题目描述

3.解题思路

1、使用双指针，让fast先走n步，然后slow和fast一起走，当fast走到结尾，slow刚好差n步到结尾，即刚好指向要删的节点

2、因为删除一个节点需要找到对应节点的前一个节点，所以让fast和slow少走一步，也就是fast.next为null就不用走了

3、采用虚拟头节点，这样程序在实际删除头节点的时候也是正常的

4.题解

/**
 * 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 | !head -> next) return NULL;
        ListNode * fast = head, *slow = head;
        for(int i = 0; i < n; i++){
            fast = fast -> next;
        }
        if(!fast){
            return head -> next;    
        }
        
        while(fast -> next){
            fast = fast -> next;
            slow = slow -> next;
        }
        slow -> next = slow -> next -> next;
        return head;
    }
};