找到单向链表的倒数第N个元素,如何在空间时间消耗上做到最小。
通常的做法是遍历一边得到长度,然后遍历第二遍,取得对应元素。
这种做法时间消耗是链表长度的2倍 - N。
或者消耗空间节省时间的方式,创建数组,遍历链表,将元素放入数组中。
这种做法时间消耗和空间消耗都是链表长度。
那么有没有更好的方式。
1.创建一个指针。
2.遍历链表,当顺序是2N的倍数时,用指针记录位置。
3.当遍历结束时,指针之后(链表长度 % 2N - N)个元素即是单向链表的倒数第N个元素。
时间消耗是链表长度 + (链表长度 % 2N - N)
空间消耗是指针的大小。
声明变量 point,
声明变量 current = 链表第一个元素
声明变量 size = 0
while(current != null){
size++
if ( size % 2n==0) {
point=current
}
current = current -> next
}
声明变量 result,
for (i=0; i < size % 2n - n; i++) {
result = point -> next
}
打印 result
分享到:
相关推荐
链表功能的一个扩展延伸,查找倒数第K个元素,是某年考研题
题目:输入一个单向链表,输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。 分析:使用两个指针,low,fast,先把fast的指针指向第k个元素,然后low和fast同时向后遍历,当fast遍历到结尾时,low...
查找链表中倒数第K个节点,源代码验证通过,两种查找方法。
只遍历一次单向链表,找到倒数第N个结点,
取单链表倒数第k个元素,包括算法描述、算法思想,算法实现等
主要介绍了python实现获取单向链表倒数第k个结点的值,结合实例形式分析了Python针对单向链表的定义、遍历、传值、判断等相关操作技巧,需要的朋友可以参考下
运行本文所述实例可实现输入一个单向链表,输出该链表中倒数第k个节点。 具体实现方法如下: /* * Copyright (c) 2011 alexingcool. All Rights Reserved. */ #include using namespace std; int array[] = {5, 7,...
解题思路一:为了实现只遍历链表一次就能找到倒数第k个节点,我们可以定义两个指针。让第一个指针先向前走k-1步,第二个指针保持不动;从第k步开始,第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离...
给你一个链表,节点有值域,计数器(表示值出现的次数,初始化为1),指针域,节点的值有重复的,去除重复的值,修改相应节点的计数器。这样做的好处就是节省的很多存储空间。 对即将参加华为机考的同学有非常大的帮助...
cpp代码-输入一个链表,输出该链表中倒数第k个结点。
* 问题:* 1. 索引单向链表中的元素* 2. 边界问题* 思路:* 1. 顺序遍历* 2. trick,两个前后间隔相差 k 的指针顺序遍历整个单向链表到末
删除单链表和双链表倒数第K个节点 删除链表的中间节点和a/b处的节点 腕单向链表和链 部分单向链表 环形单链表的约瑟夫问题 一个鉴定链表是否为回文结构 将单向链某值分割成小表、送、按右边大的形式 复制带有日常...
5、删除链表倒数第 n 个结点 6、求单向链表的中间结点 二、栈 1、Java实现顺序栈、链式栈 三、队列 1、顺序队列、链式队列 2、循环队列 四、排序算法 1、冒泡排序 2、插入排序 3、选择排序 4、归并排序 5、快速排序 ...
} 20、单链表查找倒数第k个节点题目:输入一个单向链表,输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。分析:为了得到倒数第k个结点,很自然
链表倒数第K个元素 链表的反转 链表的倒序输出 链表的中间节点 链表是否有环 链表节点的删除(不知道头结点的情况下) 链表是否相交 链表的交点 栈(顺序栈/链式栈)的数据结构及其相关算法:栈结构包含两个要素,即栈顶...
找到链表中倒数第k个节点 不同实现 设置两个指针p1、p2,让p2比p1快k个节点,同时向后遍历,当p2为空,则p1为倒数第k个节点 (-k+1+链表总数) % 链表总数 查询链表的中间节点 一个每次...
(5)、怎么查询一个单向链表的倒数第五个节点(6)、知道哪些集合类(7)、ArrayList 和 LinkedList 有什么区别(9)、HashMap 是不是
单向链表(LinkedList) 1.1链表逆序1.2去除重复项1.3两链表表示的数字相加1.4链表从中间反转1.5遍历一次找到链表的倒数第k个中断1.6发现带环链表的环入口点1.7将单链表两两反转1.8单链表的前k个元素反转1.9合并两个...