C++ 删除链表的倒数第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]

提示：

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

思路/解法

方式一

使用一个vector容器保存当前链表的所有节点即可。

TIPS：

  在删除结点的时候需要分三种情况进行讨论：

1. 当删除的结点为最后一个结点时，需要判断当前的结点是一个还是多个。
2. 当删除的结点为第一个结点时（由于第一种情况已经判断删除最后一个结点且当前总结点为一个的情况，所以这里不需要判断删除一个结点且结点个数为1的情况），直接删除并更新下一个结点即可。
3. 当删除的结点为普通节点时，直接删除并更新下一结点即可。

/**
 * 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) 
    {
        ListNode* node   = head;
        ListNode* temp   = nullptr;
        int       size   = 0;
        bool      status = false;
        std::vector<ListNode*> lists;
        while(node != nullptr)
        {
            lists.push_back(node);
            node = node->next;
        }
        
        size = lists.size();
        if(1 == n)                      //删除最后一个元素
        {
            if(1 == size)
            {
                delete lists[0];
                goto Exit;
            }
            else
            {
                delete lists[size - 1];
                lists[size - 2]->next = nullptr;
            }
        }
        else if(size == n)              //删除第一个元素
        {
            delete lists[0];
            head = lists[1];
        }
        else
        {
            lists[size - n - 1]->next = lists[size - n + 1];
            delete lists[size - n];
        }
        status = true;
    Exit:
        if(!status)
        {
            head = nullptr;
        }
        return head;
    }
};

方式二

快慢指针，一开始快慢指针都指向head结点。在删除倒数第N个结点时，先让快指针指向第N+1个结点的位置，然后慢指针跟随快指针移动，直至快指针的下一个结点为空即可，此时慢指针指向需要删除的结点的前一个结点。

TIPS：算法未释放指针指向的动态空间。

/**
 * 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) 
    {
        ListNode* quickPtr = head;
        ListNode* slowPtr  = head;
        bool      status   = false;
        int       size     = n;
        while(size)
        {
            quickPtr = quickPtr->next;
            size--;
        }

        if(nullptr == quickPtr)                  
        {
            if(1 == n)                              //链表只有一个结点
            {
                goto Exit;
            }
            else                                    //删除第一个结点
            {
                head = head->next;
            }
        }
        else
        {
            while(quickPtr->next != nullptr) 
            {
                quickPtr = quickPtr->next;
                slowPtr  = slowPtr->next;
            }

            slowPtr->next = slowPtr->next->next;    //删除结点
        }

       status = true;
    Exit:
        if(!status)
        {
            head = nullptr;
        }
        return head;
    }
};