设为首页 加入收藏

TOP

求单向链表倒序第m个元素
2014-11-23 22:13:16 来源: 作者: 【 】 浏览:1
Tags:单向 倒序 元素

原题为某游戏公司试题,大意如下: 对于一个单向链表,试写出找到它的倒序第m个元素(m >= 1)的函数,注意变量命名、注释、时间复杂度、空间复杂度。注:要求写出可编译并可以运行通过的程序代码。

这道题的常规做法或者说首先想到直觉的思路是先求得链表的长度,即元素总个数n,然后问题转化为求顺序第n-m+1个元素。但是由于这种方法要先计算长度,多了一次遍历,效率不高,而且也不高内聚,因为依赖于求长度这个运算,而这个运算完全可独立出来,为了尽量高内聚,减少对其它运算的依赖,需要进一步思考以求得更简便高效的算法,其实可以这样做,先求得顺序第m个元素,用一指针P指向这个元素,用另一指针PR指向链表的头部,现在好了,P和PR同时向右移动,直到P为空,则PR就是要求的倒序第m个元素,如果因m超越界限,则PR为空,表示没找到,这样一来,只需一次遍历就够了。C++代码描述如下
1template
2struct Node
3{
4 T data; /**////< 数据
5 Node* next; ///< 指向下一结点的指针
6} ;
7
8template
9Node* ReverseFind(Node* head, size_t m)
10{
11 size_t n = 0;
12 Node *p, *pR = NULL;
13 for (p = head;p;p = p->next)
14 {
15 if (++n == m)
16 {
17 pR = head;
18 continue;
19 }
20 if (pR)
21 {
22 pR = pR->next;
23 }
24 }
25 return pR;
26}

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇学习windows编程(6)改换entry,li.. 下一篇我也要学C语言-第十六章:返回指..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容: