【LeetCode-19 | 删除链表的倒数第N个节点】

1.jpg

2.jpg

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x): val(x), next(nullptr) {}
};

/* 双指针法: fast and slow */
class Solution {
public:
    ListNode* removeNthNode(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;

        ListNode* fast = dummy;
        ListNode* slow = dummy;

        while(n-- && fast != nullptr) {
            fast = fast->next;   // fast指针先移动n步,slow指针暂时不动
        }

        fast = fast->next;  // fast指针再向前移动一步，因为需要利用slow指针指向被删除节点的上一个节点,便于删除操作

        // fast和slow指针同时移动相同步长,直到fast指向nullptr为止
        while(fast != nullptr) {
            slow = slow->next;
            fast = fast->next;
        }
        slow->next = slow->next->next;

        return dummy->next;
    }

};