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

题目来源

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

题目解析

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 k) {
    

        return head;
    }
};

快慢指针

先检测参数：如果链表为空或者K值小于1，此时，参数无效，直接返NULL。

然后先明确一点，如果要删除链表的某个节点，实际上是需要找到要删除节点的前一个节点，因此我们可以用快慢指针找到指定位置的节点

我们可以设想假设设定了双指针 p 和 q 的话，当 q 指向末尾的 NULL，p 与 q 之间相隔的元素个数为 n 时，那么删除掉 p 的下一个指针就完成了要求。

• 设置虚拟节点 dummyHead 指向 head
• 设定双指针 p 和 q，初始都指向虚拟节点 dummyHead
• 移动 q，直到 p 与 q 之间相隔的元素个数为 n
• 同时移动 p 与 q，直到 q 指向的为 NULL
• 将 p 的下一个节点指向下下个节点

class Solution {
    

public:
    ListNode* removeNthFromEnd(ListNode* head, int k) {
    
        if(head == nullptr || k < 0){
    
            return head;
        }
        
        ListNode *dummyHead = new ListNode(0);
        dummyHead->next = head;
        
        
        ListNode *slow = dummyHead;
        ListNode *fast = dummyHead;
        for (int i = 0; i < k + 1; ++i) {
    
            fast = fast->next;
        }
        while (fast){
    
            fast = fast->next;
            slow = slow->next;
        }
        
        ListNode *delNode = slow->next;
        slow->next = delNode->next;
        delete delNode;
        
        ListNode* ret = dummyHead->next;
        delete dummyHead;
        
        return ret;
    }
};