随笔-156  评论-223  文章-30  trackbacks-0
求单向链表倒序第m个元素
   原题为某游戏公司试题，大意如下：  对于一个单向链表，试写出找到它的倒序第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 (++n == 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 春秋十二月 阅读(2502) 评论(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   知识库   博问   管理


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 春秋十二月