876. 链表的中间结点
创始人
2025-05-31 07:06:02

文章目录

  • 题目
  • 思路1(暴力求解)
  • 思路2(快慢指针)
  • 总结

题目

在这里插入图片描述

思路1(暴力求解)

既然让我们求中间的节点，我们可以先遍历一遍求出整个链表的节点个数N，再遍历到N/2+1，当前位置就是中间节点的位置，虽然这样的时间复杂度是O(n)但是这样需要遍历两次，我们有一个更巧妙的方法

思路2(快慢指针)

我们可以i定义两个指针，fast和slow，fast每次走2个节点，slow每次走1个节点
如果是奇数个节点的话，当fast的下一个节点是空节点时，slow走到的当前节点就是中间节点，
如果是偶数个节点的话，当fast当前的节点是空节点时，slow走到的当前节点就是中间节点
在这里插入图片描述
代码实现

struct ListNode* middleNode(struct ListNode* head){if (head == NULL || head->next == NULL) return head;struct ListNode* fast = head, *slow = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}

在这里插入图片描述

总结

快慢指针是一种常用的链表指针操作技巧，可以在链表中解决很多问题。下面是一些可以使用快慢指针的常见场景：

  1. 判断链表是否有环：快慢指针可以用来判断一个链表是否有环。将慢指针移动一步，快指针移动两步，如果存在环，两个指针最终会相遇。这个技巧被称为快慢指针法或者龟兔赛跑算法。

  2. 查找链表的中间节点：使用快慢指针可以查找链表的中间节点。将慢指针移动一步，快指针移动两步，当快指针到达链表末尾时，慢指针刚好在链表中间。

  3. 链表倒数第k个节点：使用快慢指针也可以查找链表的倒数第k个节点。将快指针移动k-1步，然后将快慢指针一起移动，当快指针到达链表末尾时，慢指针所指的节点就是倒数第k个节点。

  4. 删除链表的倒数第n个节点：可以使用快慢指针删除链表的倒数第n个节点。先将快指针移动n步，然后将快慢指针一起移动，当快指针到达链表末尾时，慢指针所指的节点就是要删除的节点。

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：5.docker入门到精通—安装redis集群（理论）

下一篇：AES加密算法原理及C++代码，每步均有相应代码

相关内容

热门资讯

英国最强逆袭巨头：从杂货铺起家... 从19世纪伦敦一家经营贝壳贸易的小店，到世界石油巨头之一，壳牌——这家穿越两次世界大战、多次能源革命...
他64岁了，花了16年，只为一... 作 者：正风来 源：正和岛（ID：zhenghedao）本文摘编自正和岛、陈为、夏昆著《价值观的力量...
冯仑：2025年还能买房吗？ ... 封面图 |《造房子的人》剧照01问：冯叔，我在一线城市生活，手里有点闲钱，想做点投资，但不知道投什么...
解决企业AI落地难题：司马阅秉... “技术只是手段，解决企业的问题才是目的。AI本质上是一种新的生产力工具，而不是用来“炫技”的噱头。企...
中证A500指数样本股调整已正... 6月16日早盘，三大指数低开后震荡翻红，CPO等概念继续活跃。主要宽基ETF中，A500指数ETF（...
德国展台搭建应选择优质环保材料 德国展台搭建应选择优质环保材料?德国民众环保意识强烈，法规对环保要求严苛，在德国展台搭建时选择优质环...
聚星科技：6月13日融资买入1... 证券之星消息，6月13日，聚星科技（920111）融资买入198.5万元，融资偿还185.52万元，...
港股奢侈品品牌股集体拉升，英皇... 港股奢侈品品牌股集体拉升，英皇钟表珠宝涨超9%，周大福涨超6%，周生生涨超4%，普拉达涨近3%。 ...
顺钠股份：6月13日融资买入4... 证券之星消息，6月13日，顺钠股份（000533）融资买入4498.44万元，融资偿还4490.18...
雷军官宣：小米YU7将于月底发... 6月16日，雷军在微博发文表示：大家非常期待的小米YU7，将于6月底发布。还有很多重磅新品同场一起发...
签约项目176个　中非经贸博览... 6月15日，第四届中国—非洲经贸博览会落下帷幕。记者在成果通报会上获悉，本届博览会经组委会审核发布的...
网络游戏概念持续走强 冰川网络... 6月16日，网络游戏概念持续走强，冰川网络涨逾8%，电魂网络涨逾7%，盛天网络、吉比特等涨幅居前。
宁德时代，重大调整！ 宁德时代... 深交所发布公告称，将宁德时代调入深港通下的港股通标的证券名单，自6月16日起生效。
可控核聚变概念活跃，永鼎股份领... 6月16日，可控核聚变概念活跃，永鼎股份涨逾7%，精达股份涨逾6%，炬光科技、利柏特、王子新材、哈焊...
泡泡玛特，一度大跌近5%！ 泡... 港股泡泡玛特早盘跳水，盘中一度跌近5%，现跌幅收窄至0.44%。
沪指放量失守多条均线 短线或重... 解锁【第一财经智享会员】实时解读市场动态，把握投资先机。【第一财经智享会员专属】晨会博弈【今日早盘】...
近4日共累计“吸金”超3300... 6月16日，三大指数集体低开后震荡走高。截至发稿，上证科创板人工智能指数涨0.35%。相关ETF方面...
“低空经济”的蛋糕，哪些城市能... “低空经济”的蛋糕正逐渐崛起，众多城市有望分得一杯羹。北京凭借其雄厚的科技实力和庞大的市场需求，在低...
北证50涨逾1%，科力股份涨逾... 6月16日，北证50涨逾1%，科力股份涨逾25%，凯添燃气、易实精密、瑞奇智造涨逾10%。
CPO概念拉升，新易盛股价创年... 6月16日，CPO概念拉升，太辰光涨逾8%，致尚科技、永鼎股份涨逾6%，博创科技、德科立、炬光科技等...
斩获多项重量级营销大奖，爱玛科... 据权威数据显示，2025年一季度，我国电动两轮车市场呈现出全面增长的态势，除了技术突破、全球化布局之...
雷军：小米yu7将在6月底发布 6月16日，雷军发文称小米yu7将在6月底发布，同场发布的还有小米平板75Pro。 来源：@雷军
杭州一泡泡玛特开业当天闭店，是... 6月15日，原定于今天开业的泡泡玛特杭州某店，开业没多久就宣布闭店，门店表示“内部整改问题，开业延期...
今日权益登记！港股红利低波ET... 区域冲突再升级，全球风险偏好下行。港股红利低波ETF(520550)持续获资金追逐，截至6月13日，...
“小米方法论”研究Ⅰ：雷军何以... 文｜锦缎 就在近日，雷军出席了2025年小米的投资者大会。今年是小米成立的十五周年，除了回答投资者...
这年头，连中餐都能“1块钱旋转... 总第4248期作者 |餐饮老板内参内参君1.8凉面、3.8麻婆豆腐川菜也能“旋转”了转转小火锅吃多了...
A股三大指数全线翻红，稳定币概... 6月16日，A股三大指数全线翻红，稳定币概念股爆发，油气、AI应用、新能源板块涨幅居前。
单日“吸金”3.3亿元，港股创... 6月16日，港股创新药概念股再度活跃。相关ETF中，港股创新药ETF（159567）截至发稿涨1.3...
泡泡玛特一度跌近5% 泡泡玛特... 6月16日电，泡泡玛特盘中一度跌近5%，截至发稿，跌超2%。
歼-35A将亮相巴黎航展，航空... 6月16日早盘，国证航天指数截至发稿跌0.37%，成分股中，国睿科技涨超3%，纳睿雷达、华秦科技、振...