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

  这道题的常规做法或者说首先想到直觉的方法M1是先求得链表的长度,即元素总个数n,然后问题转化为求顺序第n-m+1个元素。下面给出第2种方法M2:先求得顺序第m个元素,用一指针P指向这个元素,用另一指针PR指向链表的头部,现在好了,P和PR同时向右移动,直到P为空,则PR就是要求的倒序第m个元素,如果因m超越界限,则PR为空,表示没找到,这样一来,只需一次循环就够了。C++代码描述如下
 1 template<typename T>
 2 struct Node
 3 {  
 4     T  data;    /**////< 数据
 5     Node* next;  ///< 指向下一结点的指针
 6 } ;

 7 
 8 template<typename T>
 9 Node<T>* ReverseFind(Node<T>* head, size_t m)
10{
11    size_t  n = 0;
12    Node<T> *p, *pR = NULL;
13    for (p = head;p;p = p->next)
14    {
15        if (++== m)
16        {
17            pR = head;
18            continue;
19        }

20        if (pR)
21        {
22            pR = pR->next;
23        }

24    }

25    return pR;
26}
  现在分析这2种方法的时间复杂度,假设链表元素个数为N,所求倒序为第M元素,N>=M,则M1方法为0(N)+0(N-M)=0(2N-M),M2方法为O(M)+O(N-M)=0(N),因此M2快于M1。
posted on 2011-06-24 11:40 春秋十二月 阅读(2477) 评论(11)  编辑 收藏 引用 所属分类: Algorithm

评论:
# re: 求单向链表倒序第m个元素 2011-06-24 12:30 | coreBugZJ
赞一个  回复  更多评论
  
# re: 求单向链表倒序第m个元素 2011-06-24 16:45 | paw
额,,考研数据结构题。。。  回复  更多评论
  
# re: 求单向链表倒序第m个元素 2011-06-24 23:57 | 鱼吃猫
顶一个~  回复  更多评论
  
# re: 求单向链表倒序第m个元素[未登录] 2011-06-25 12:06 | 英雄哪里出来
不错,赞一个~~  回复  更多评论
  
# re: 求单向链表倒序第m个元素[未登录] 2011-06-25 13:39 | kaka
第一个指针从头移动到m,和第二个指针一起再移动到尾部。

第二个指针和第一个指针一起移动。

只不过将一个指针大于一次遍历的操作分解成两个指针操作。

这样算是一次遍历?  回复  更多评论
  
# re: 求单向链表倒序第m个元素 2011-06-25 23:36 | 梦提
是一次遍历,因为时间上是同步的。@kaka
  回复  更多评论
  
# re: 求单向链表倒序第m个元素 2011-06-26 08:47 | 搞笑
这个也太搞笑了?效率是一样的,还竟然有:“这样效率不高”的说法。  回复  更多评论
  
# re: 求单向链表倒序第m个元素 2011-06-26 13:54 | temp
是一样的,两个指针分别遍历。  回复  更多评论
  
# re: 求单向链表倒序第m个元素 2011-06-26 15:24 | Arcko
貌似需要遍历的确实是一样的多,不过换个思路考虑也很好  回复  更多评论
  
# re: 求单向链表倒序第m个元素 2011-06-27 10:09 | megadeath
使用递归方式(示例代码,无任何错误检查),把for语句也消隐掉。

static int nOrder = 0;
template <typename ITERATOR, typename UINT>
void F(ITERATOR begin, ITERATOR end, UINT M)
{
ITERATOR it = begin;
if (begin != end)
F(++begin, end, M);

if (++nOrder == ++M)
cout << *it << endl;
}
  回复  更多评论
  
# re: 求单向链表倒序第m个元素 2011-07-01 11:06 | 有雾
我也感觉效率一样的。第二个里面,同样要把P移动到链表尾,这样才能获得size。所以不存在O(M),同样是O(N)啊。@搞笑
  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理