链表专项练习题四 | 删除链表倒数第n个结点


问题描述

给定一个链表,随机删除链表中倒数第n个结点,并返回链表的头结点。
链表中的结点个数大于等于n
示例:
给出链表 1->2->3->4->5->null 和 n = 2
删除倒数第2个结点之后,最终得到链表 1->2->3->5->null
要求:
O(n)时间复杂度,一次遍历实现。

题目分析

既然要删除链表的倒数第n个结点,那么就需要先找出链表的倒数第n+1个结点,然后修改这个结点的指向为next->next。
题目要求一次遍历实现,我们可以使用“双指针法”,设置两个指针p1和p2;p1先出发,走到第n+1个结点时,p2再出发。这样,当p2走到链表的尾结点时,p1指向的正好是倒数第n+1个结点。

实现代码

NodeList removeNodeFromEnd( NodeList Head , int n)
{
    NodeList preNode = Head;
    NodeList curNode = Head;
    for(int i=0; i<n; i++){
        curNode = curNode->next;
    }
    if(curNode == null){
        return preNode->next;
    }
    while(curNode!=NULL){
        curNode = curNode->next;
        preNode = preNode->next;
    }
    preNode->next = preNode->next->next;
    return Head;
}

参考链接

LeetCode - 删除链表的倒数第N个节点
删除链表中倒数第n个节点

本文发表于2018年11月14日 21:24
阅读 100 讨论 0 喜欢 0

讨论

周娱

君子和而不同
按照自己的方式,去度过人生

5151 1438887
抢先体验

扫码体验
趣味小程序
文字表情生成器

加入组织

扫码添加周娱微信
备注“加入组织”
邀请进开发群

闪念胶囊

“决定我们成为什么样的人,不是我们的能力,而是我们的选择。”

让一个团队走向平庸的最佳方式,是让成员们持续地干那些不让他们感到自豪的事情。

最近1 2年发现成长的最好方式是研究开源的项目,自己实践。成长速度非常的快,一个好的项目需要考虑的细节很多。

不积跬步无以至千里,越焦虑越要扎实干。

不要试图鹤立鸡群,趁早离开那群鸡!

程序员过节需要的不是美女、不是美食、不是不加班!他们需要的是写代码,一群人写、往死里写、通宵写!!那种暗流涌动的狂欢,远比虚无庸俗的食色更让他们振奋!! by芋头

面试的时候,常常会问数组和链表的区别,很多人都回答说,“链表适合插入、删除,时间复杂度 O(1);数组适合查找,查找时间复杂度为 O(1)”。 实际上,这种表述是不准确的。数组是适合查找操作,但是查找的时间复杂度并不为 O(1)。即便是排好序的数组,你用二分查找,时间复杂度也是 O(logn)。 所以,正确的表述应该是,数组支持随机访问,根据下标随机访问的时间复杂度为 O(1)。

找一个bug就好比从一泡烂泥里找一条泥鳅,写一个bug就好比往一泡烂泥里丢一条泥鳅进去

数据结构在某种程度上和设计模式类似,都是前辈的武功套路。不同的是,设计模式是近几十年的卓越程序员的智慧结晶,而数据结构是几百上千年的无数科学家、数学家的智慧沉淀,更加具有深厚的背景。

Copyright © 2016 - 2018 Cion.
All Rights Reserved.
备案:鲁ICP备16007319号.