写点什么

算法题学习 --- 删除链表的倒数第 n 个节点

作者:桑榆
  • 2022-11-14
    广东
  • 本文字数:1180 字

    阅读完需:约 4 分钟

题目

描述

给定一个链表,删除链表的倒数第 n 个节点并返回链表的头指针 例如,

给出的链表为: 1→2→3→4→5, n= 2. 删除了链表的倒数第 n 个节点之后,链表变为 1→2→3→5.

数据范围: 链表长度 0≤n≤1000,链表中任意节点的值满足 0≤val≤100

要求:空间复杂度 O(1),时间复杂度 O(n) 备注:

题目保证 n 一定是有效的

示例 1

输入:{1,2},2    返回值:{2} 
复制代码

分析

考虑特殊情况

在进行问题分析过程前,我们先考虑一下特殊情况,那么在这道问题中,有哪些情况是特殊的呢?

不难发现,如下情况:

  • 如果输入的头结点为空,那么返回 nullptr 即可

考虑一般情况

这个问题实际上是在寻找链表倒数第 n 个节点的基础上引入的,

寻找链表的第 n 个节点的方式:

假设链表长度为 length,我们需要知道怎么才能走 length-n 步,这样考虑,我们设置快慢指针,快指针先走 n 步,然后慢指针再和快指针一起走,这样,当快指针走到链表末尾时,慢指针恰好走了 length-n 步,也就直接返回慢指针的节点就好了。

也就是说我们要先找到倒数第 n 个节点,然后同时记录它的前驱节点,然后做删除节点的操作即可,如下:

  • step 1:给链表添加一个表头,处理删掉第一个元素时比较方便。

  • step 2:准备一个快指针,在链表上先走 n 步。

  • step 3:准备慢指针指向原始链表头,代表当前元素,前序节点指向添加的表头,这样两个指针之间相距就是一直都是 n。

  • step 4:快慢指针同步移动,当快指针到达链表尾部的时候,慢指针正好到了倒数 n 个元素的位置。

  • step 5:最后将该节点前序节点的指针指向该节点后一个节点,删掉这个节点。

代码示例

注意,这里我们增加了一个链表头 pReturn,避免需要删除头结点的情况;

使用 pPre 不断记录 pSlow 的前驱,以便后面删除 pSlow 节点。

/** * struct ListNode { *        int val; *        struct ListNode *next; * }; */
class Solution {public: /** * * @param head ListNode类 * @param n int整型 * @return ListNode类 */ ListNode* removeNthFromEnd(ListNode* head, int n) { // write code here if(nullptr == head){ return nullptr; }
ListNode *pReturn = new ListNode(-1); pReturn->next = head;
// find the Nth node from End ListNode* pQuick = head; ListNode* pSlow = head; ListNode* pPre = pReturn; for(int i =0;i<n;++i){ if(nullptr == pQuick){ return nullptr; } pQuick = pQuick->next; }
while(nullptr != pQuick){ pQuick = pQuick->next; pPre = pSlow; pSlow = pSlow->next; }
// delete the pSlow pPre->next = pSlow->next;
return pReturn->next; }};
复制代码


发布于: 刚刚阅读数: 3
用户头像

桑榆

关注

北海虽赊,扶摇可接;东隅已逝,桑榆非晚! 2020-02-29 加入

Android手机厂商-相机软件系统工程师 爬山/徒步/Coding

评论

发布
暂无评论
算法题学习---删除链表的倒数第n个节点_算法题_桑榆_InfoQ写作社区