这道题目有两种算法,但无论哪种算法,都要考虑单链表少于n个元素的情况。这里假设要寻找倒数第4个元素。
第1种算法,建立两个指针,第一个先走4步,然后第2个指针也开始走,两个指针步伐(前进速度)一致。
static Link GetLast4thOne(Link head) {
Link first = head;
Link second = head;
for (int i = 0; i < 4; i++) {
if (first.Next == null) throw new Exception("Less than 4 elements");
first = first.Next;
}
while (first != null) {
first = first.Next;
second = second.Next;
}
return second;
}
第2种算法,做一个数组arr[4],让我们遍历单链表,把第0个、第4个、第8个„„第4N个扔到arr[0],把第1个、第5个、第9个„„第4N+1个扔到arr[1],把第2个、第6个、第10个„„第4N+2个扔到arr[2],把第3个、第7个、第11个„„第4N+3个扔到arr[3],这样随着单链表的遍历结束,arr中存储的就是单链表的最后4个元素,找到最后一个元素对应的arr[i],让k=(i+1)%4,则arr[k]就是倒数第4个元素。
static Link GetLast4thOneByArray(Link head) {
Link curr = head;
int i = 0;
Link[] arr = new Link[4];
while (curr.Next != null) {
arr[i] = curr.Next;
curr = curr.Next;
i = (i + 1) % 4;
}
if (arr[i] == null) throw new Exception("Less than 4 elements");
return arr[i];
}
分享到:
相关推荐
很多大公司的面试题,查找单链表倒数第N个节点
C CODE FOR :只遍历一遍找出单链表的倒数第K个节点
取单链表倒数第k个元素,包括算法描述、算法思想,算法实现等
数据结构单链表练习:删除单链表的倒数第n个节点。 博客地址:https://blog.csdn.net/qq_39400324/article/details/122640229
链表功能的一个扩展延伸,查找倒数第K个元素,是某年考研题
19. 删除链表的倒数第N个节点 难度: 中等 题目分析: 链表中的题目,指针相当于免费资源,可以根据需要增加。双指针法、快慢指针法在环形链表,应用很多。 解法一: # 对于这种题目,循环结束条件设为快指针到达...
通过一次遍历找到单链表中倒数第 n 个节点。
单链表中查找倒数第n个元素2010-07-30通过一次遍历找到单链表中倒数第n个节点,链表可能相当大,可使用辅助空间,但是辅助空间的数目必须固定,不能和n有关。
一次遍历单链表删除倒数第n个节点的问题,跟删除某个节点的前一个节点是一个思路
输出单链表倒数第K个结点值.cpp
题目:输入一个单向链表,输出该链表中倒数第k个结点。...分析:使用两个指针,low,fast,先把fast的指针指向第k个元素,然后low和fast同时向后遍历,当fast遍历到结尾时,low正好遍历到倒数第k个。
javaScript实现一个单链表,找到单链表中的倒数第n个节点
cout倒数第"个元素为"<<little->data; } void main() { int a[100]; int length; int l; int k=2; cout请输入单链表的长度:"; cin>>length; for(int i=0;i;i++) { a[i]=i+1; } cout; LinkList...
本文提供了找出链表倒数第n个节点元素的二个方法,其中一个方法是JAVA代码实现
2.找出单链表的倒数第4个元素 3.找出单链表的中间元素 4.删除无头单链表的一个节点 5.两个不交叉的有序链表的合并 6.有个二级单链表,其中每个元素都含有一个指向一个单链表的指针。写程序把这个二级链表称一级...
删除链表中倒数第N个结点后,返回结果链表的首结点
找出单链表的倒数第4个元素 3.找出单链表的中间元素 4.删除无头单链表的一个节点 5.两个不交叉的有序链表的合并 6.有个二级单链表,其中每个元素都含有一个指向一个单链表的指针。写程序把这个二级链表称一级...
主要为大家详细介绍了python实现单链表中删除倒数第K个节点的方法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
主要介绍了C++实现单链表删除倒数第k个节点的方法,结合实例形式分析了C++单链表的定义、遍历及删除相关操作技巧,需要的朋友可以参考下
只遍历一次单向链表,找到倒数第N个结点,