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

题目描述

思路及解法

1.创建虚拟头节点dummy指向并将其next指向head；指针fast、slow指向dummy；
2.遍历链表获取其长度len；
3.先使fast走n + 1步，再使（当fast不为空时）slow与fast同时往后每一次移动一位；
4.删除节点slow -> next = slow -> next -> next;
5.返回dummy -> next;(注意：在该代码中创建dummy节点也是为了更好的处理删除的节点是头节点的情况)

复杂度

时间复杂度:

$O(n)$；其中$n$为链表的长度

空间复杂度:

$O(1)$

Code

/**
 * 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:
    /**
     * Two pointer
     * @param head The head node of linked list
     * @param n The penultimate NTH number
     * @return ListNode*
     */
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* p = head;
        int len = 0;
        while (p != nullptr) {
            len++;
            p = p -> next;
        }
        if (n > len) {
            return nullptr;
        }
        ListNode* dummy = new ListNode(INT_MIN);
        dummy -> next = head;
        ListNode* fast = dummy;
        ListNode* slow = dummy;
        for (int i = 0; i < n + 1; ++i) {
            fast = fast -> next;
        }
        while (fast != nullptr) {
            slow = slow -> next;
            fast = fast -> next;
        }
        slow -> next = slow -> next -> next;
        return dummy -> next;
    }
};