目录

第一站 LeetCode 新手村

前言

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

题目描述

解题思路

代码

总结

题目来源

第一站 LeetCode 新手村

前言

最近玩OJ赛，发现对算法的理解还需要更加扎实，code能力还可以进一步提升，所以做这样一个算法的系列文章，用于记录学习心得，交流经验，更好地进步和成长。也欢迎小伙伴们来给笔者留言，提问

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

题目描述

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

示例1

输入：nums = [1,2,3,4]

输出：[1,3,6,10]

解释：动态和计算过程为 [1, 1+2, 1+2+3, 1+2+3+4]

示例 2

输入：nums = [1,1,1,1,1]
输出：[1,2,3,4,5]
解释：动态和计算过程为 [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1] 。

 示例 3

输入：nums = [3,1,2,10,1]
输出：[3,4,6,16,17]

提示

• 1 <= nums.length <= 1000
• -10^6 <= nums[i] <= 10^6

解题思路

预知

LeetCode是核心代码模式，所以只需要考虑核心算法，输入由系统自动完成，最后的输出以return返回；

思路

利用栈存储链表结点，寻找到倒数第n个元素的前一个，然后指向该元素next的next，刚好跳过倒数第n个元素，具体的实现思路请参考代码和注释；

空说无意，还是代码来的生动呐！

不熟悉栈特性的小伙伴可以看leetcode官方讲解，更加详细，入口放在下方；也欢迎给笔者留言，有问必答；

力扣

代码

C++

/**
 * 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* dummy = new ListNode(0, head); //哑结点，下一结点指向head
        stack<ListNode*> stk;  //定义栈  压入栈中的是链表结点
        ListNode* cur = dummy;
        while(cur){
            stk.push(cur); //元素入栈
            cur = cur->next;
        }

        for(int i=0;i<n;i++){
            stk.pop();  //元素出栈   弹出该元素并没有消失，只是不存在栈中了，原来占用的存储空间仍然存在
        }               //这里调用栈的目的，就是找到倒数第n个元素
        ListNode* prev = stk.top();  //等于它栈顶的元素
        prev->next = prev->next->next;  //这里解释下为什么可以直接指向，因为压入栈中的是链表结点
                                        //所以栈中的各元素仍然会是以一个单链表的形式存在，只不过head被存到了栈的最底部
        //下面这三步的目的其实就是释放哑结点
        ListNode* ans = dummy->next;    
        delete dummy;  //释放哑结点
        return ans;
        // return dummy->next;  //不释放哑结点，直接指向它的下一个结点输出也是可以的
    }
};

//笔者认为，调栈的方法有些臃肿，时间复杂其实并没有降低，还占用了空间

总结

以上就是今天要讲的内容，本文仅仅简单讲解了《19. 删除链表的倒数第 N 个结点》这一题目，对利用栈的先进后出特性操作链表有了进一步的掌握。

题目来源

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/running-sum-of-1d-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处