链表#中等#删除链表的倒数第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]

正文

/**
 * 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) {

    }
};

解法1 删除顺数len-n+1个节点

删除倒数第n个节点，即删除顺数len-n+1个节点：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* curr = head;

        int len = 0;
        while(curr) {
            ++len;
            curr = curr->next;
        }
        // cout << len << endl;
        int del_n = len - n + 1;
        // cout << del_n << endl;

        // three situations
        // del_n = 1, delete the first element
        if (del_n == 1) {
            // cout << "del_n == 1" << endl;
            head = head->next;
            return head;
        }
        // del_n = len, delete the end element
        if (del_n == len) {
            // cout << "del_n == len" << endl;
            int idx = 0;
            curr = head;
            while(curr) {
                ++idx;
                if (idx == del_n - 1) {

                    // cout << "idx == del_n - 1" << endl;
                    curr->next = nullptr;
                }
                if (idx != del_n)
                    curr = curr->next;
            }
            return head;
        }
        // 1 < del_n < len, delete the inter element
        if (1 < del_n && del_n < len) {
            // cout << "1 < del_n && del_n < len" << endl;
            int idx = 0;
            curr = head;
            while(curr) {
                ++idx;
                if (idx == del_n - 1)
                    curr->next = curr->next->next;
                curr = curr->next;
            }
            return head;
        }
        return nullptr;
    }
};

首先获取链表长度，计算需要删除的顺数第len-n+1个节点，之后分三种情况讨论：

第一种：删除第一个节点

第二种：删除最后一个节点

第三种：删除中间的节点

即可。