链表训练1:删除单链表的第K个节点
题目描述
在单链表中删除倒数第 K 个节点
要求
如果链表的长度为 N, 时间复杂度达到 O(N), 额外空间复杂度达到 O(1)
解答
删除的时候会出现三种情况:
1、不存在倒数第 K 个节点,此时不用删除
2、倒数第 K 个节点就是第一个节点
3、倒数第 K 个节点在第一个节点之后
所以我们可以用一个变量 sum 记录链表一共有多少个节点。
如果 num < K,则属于第一种情况。
如果 num == K,则属于第二中情况。
如果 num > K, 则属于第三种情况,此时删除倒数第 K 个节点等价于删除第 (num – k + 1) 个节点。
代码如下:
对于这种链表题,思路其实很简单,但如果让你来写代码,你不一定就能写对,所以呢,大家切勿眼高手低,一定要自己实现一遍,并且这道题,也属于面试中的高频题。
如果你能提供其他代码版本,欢迎评论区给出哈。
如果喜欢本网站{https://www.iamshuaidi.com), 那么可以把该网站分享给其他人,帅地正在疯狂更新中….
评论(6)
你这个代码有问题,最后应该是 num-k-1!=0 才对
你这个代码有问题,最后应该是 num-k-1!=0 才对
感谢提醒,确实应该是 num-k-1!=0 ,以更改
强烈建议帅地挂图,这样能很好的让人理解
后续教程尽量挂图