问题: 给定一个链表,在只遍历一遍的前提下查找倒数第n个元素。数据开销要求尽可能小。
思路:
设置两个哨兵指针,第一个指针先移动n个位置,然后第二个指针再从头结点与第一个指针一起移动。这样第一个指针跟第二个指针之间的距离为n个结点长度,因此当第一个指针移动到尾部的时候,第二个指针即指向倒数第n个结点。
代码:
#include <iostream>
using namespace std;
struct Node
{
Node* next;
int flag;
};
Node* reverse_find(Node* pt_head, int n)
{
Node* pt_first_sentinel = pt_head;
Node* pt_second_sentinel = pt_head;
for (int i = 0; i < n; ++i)
{
pt_first_sentinel = pt_first_sentinel->next;
}
while (pt_first_sentinel != NULL)
{
pt_first_sentinel = pt_first_sentinel->next;
pt_second_sentinel = pt_second_sentinel->next;
}
return pt_second_sentinel;
}
void link_list_test()
{
Node* pt_head = new Node;
Node* pt_node = pt_head;
pt_head->flag = 1;
for (int i = 2; i <= 8; ++i)
{
Node* pt_new_node = new Node;
pt_new_node->flag = i;
pt_node->next = pt_new_node;
pt_node = pt_new_node;
}
pt_node->next = NULL;
Node* result = reverse_find(pt_head, 8);
cout << result->flag << endl;
}
int main()
{
link_list_test();
return 0;
}
分享到:
相关推荐
查找链表中倒数第K个节点,源代码验证通过,两种查找方法。
删除链表中倒数第N个结点后,返回结果链表的首结点
链表功能的一个扩展延伸,查找倒数第K个元素,是某年考研题
python 删除链表中倒数第N个节点(csdn)————程序
NULL 博文链接:https://128kj.iteye.com/blog/1748487
创建一个链表,编程实现查找它的倒数第k个节点
19. 删除链表的倒数第N个节点 难度: 中等 题目分析: 链表中的题目,指针相当于免费资源,可以根据需要增加。双指针法、快慢指针法在环形链表,应用很多。 解法一: # 对于这种题目,循环结束条件设为快指针到达...
只遍历一次单向链表,找到倒数第N个结点,
python python_leetcode面试题解之删除链表的倒数第N个节点
题目:输入一个单向链表,输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。 分析:使用两个指针,low,fast,先把fast的指针指向第k个元素,然后low和fast同时向后遍历,当fast遍历到结尾时,low...
初始化并建立单链表 遍历链表数据 查找倒数第N个数据 查找中间数据
19. 删除链表的倒数第N个节点19. 删除链表的倒数第N个节点 — Medium题目描述给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。示例
本文提供了找出链表倒数第n个节点元素的二个方法,其中一个方法是JAVA代码实现
很多大公司的面试题,查找单链表倒数第N个节点
删除链表的倒数第 N 个结点.md
(1)在链表中第i个位置插入新的数据元素,显示链表; (2)删除链表的第i个元素,输出该元素,显示链表; 三)就地置逆+求最大最小值 在题目(一)的单链表中: (1)将链表就地逆置 ,显示链表; (2)求链表中的最大,...
单链表中查找倒数第n个元素2010-07-30通过一次遍历找到单链表中倒数第n个节点,链表可能相当大,可使用辅助空间,但是辅助空间的数目必须固定,不能和n有关。
0019-删除链表的倒数第N个节点.py
# 删除链表的倒数第N个节点 题目链接给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。示例:给定一个链表: 1->2->3->4->5, 和
python_leetcode面试题解之第19题删除链表的倒数第N个结点