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

力扣题目链接

给你一个链表，删除链表的倒数第n个结点，并且返回链表的头结点。

示例1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：
输入：head = [1], n = 1
输出：[]

示例 3：
输入：head = [1,2], n = 1
输出：[1]

双指针法，对于删除头结点的情况单独处理，时间复杂度 O ( n ) O(n) O(n)，空间复杂度 O ( 1 ) O(1) O(1)：

#include 
#include 

using namespace std;

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:
    static ListNode *removeNthFromEnd(ListNode *head, int n) {
        ListNode *right = head;
        ListNode *left = head;
        ListNode *tmp = nullptr;

        while(n--) {
            right = right->next;
        }

        if (!right) {
            tmp = head;
            head = head->next;
            delete tmp;
            return head;
        }

        while(right->next) {
            right = right->next;
            left = left->next;
        }


        tmp = left->next;
        left->next = tmp->next;
        delete tmp;

        return head;
    }
};

int main() {
    vector data = {2, 3, 4, 5};
    ListNode *head = new ListNode(1); // 头结点
    ListNode *cursor = head; // 游标指针

    
    for (auto i : data) {
        ListNode *new_node = new ListNode(i);
        cursor->next = new_node;
        cursor = cursor->next;
    }

    
    head = Solution::removeNthFromEnd(head, 2);

    while (head != nullptr) {
        cout << head->val << endl;
        ListNode * tmp = head;
        head = head->next;
        free(tmp);
    }
}

双指针法，采用虚拟头结点，所有情况统一处理，时间复杂度 O ( n ) O(n) O(n)，空间复杂度 O ( 1 ) O(1) O(1)：

#include 
#include 

using namespace std;

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:
    static ListNode *removeNthFromEnd(ListNode *head, int n) {
        ListNode *dummy_head = new ListNode(); // 虚拟头结点
        ListNode *right = dummy_head;
        ListNode *left = dummy_head;

        dummy_head->next = head;

        while(n--) {
            right = right->next;
        }

        while(right->next) {
            right = right->next;
            left = left->next;
        }

        ListNode *tmp = left->next;
        left->next = tmp->next;
        delete tmp;

        return dummy_head->next;
    }
};

int main() {
    vector data = {2};
    ListNode *head = new ListNode(1); // 头结点
    ListNode *cursor = head; // 游标指针

    
    for (auto i : data) {
        ListNode *new_node = new ListNode(i);
        cursor->next = new_node;
        cursor = cursor->next;
    }

    
    head = Solution::removeNthFromEnd(head, 2);

    while (head != nullptr) {
        cout << head->val << endl;
        ListNode * tmp = head;
        head = head->next;
        free(tmp);
    }
}