下午腾讯笔试题 2010-4-8

genlic 2010-04-08 07:56:36

出题的大致函数声明：
node fun(node * head, int index)，要我们实现函数里面的方法。
其中node是一个单向链表。
要实现的功能：返回倒数的第n个节点。
怎样优化，看大家各自发挥~

...全文

9010 156 打赏收藏转发到动态举报

写回复

用AI写文章

156 条回复

切换为时间正序

请发表友善的回复…

发表回复

donghong2007415 2011-06-22

打赏
举报

学习了

sun152121 2011-05-13

打赏
举报

想法都很好~受教了~

lwx496 2011-04-22

打赏
举报

[Quote=引用 153 楼 sjunhot_sky 的回复:]
引用 100 楼 jxgzlxj 的回复:
引用 5 楼 xuwenq 的回复:
这也是常见的问题了
一般设置两个指针p1,p2
首先p1和p2都指向head
然后p2向前走n步，这样p1和p2之间就间隔n个节点
然后p1和p2同时向前步进，当p2到达最后一个节点时，p1就是倒数第n个节点了

你这有个问题，就是当n大于整个表长的一半时这种算法不管用了。

同样可以解决
[/Quote]

我也觉得n大于整个表长的一半时，也没什么问题

sjunhot_sky 2011-03-27

打赏
举报

[Quote=引用 100 楼 jxgzlxj 的回复:]
引用 5 楼 xuwenq 的回复:
这也是常见的问题了
一般设置两个指针p1,p2
首先p1和p2都指向head
然后p2向前走n步，这样p1和p2之间就间隔n个节点
然后p1和p2同时向前步进，当p2到达最后一个节点时，p1就是倒数第n个节点了

你这有个问题，就是当n大于整个表长的一半时这种算法不管用了。
[/Quote]
同样可以解决

ice__man 2010-11-06

打赏
举报

可以递归整个链表，依次获取每个节点处往后的链表长度。
如果当前节点长度是要返回的位置，则保存当前节点位置。

没调试过。不知道是否可行。



node* result = NULL;



node* fun(node * head, int index)

{

  if ((NULL == head) || (0 == index))

  {

    return head;

  }

  (void)travel_list(head, n);

  return result;

}



int travel_list(node* cur, int n)

{

    int length = 0;

    if (NULL == cur)

    {

        return 0;

    }

    int len = travel_list(cur->next, n) + 1;  // 获取余下节点个数，然后加1

    if (n == len)

    {

        result = cur;             // 如果当前链表长度为n，则保存当前节点；

    }

    return len;

}

蔷薇理想人生 2010-10-09

打赏
举报

好，学习了。

shwarpine 2010-07-09

打赏
举报

Mark.谢谢好方法。
[Quote=引用 5 楼 xuwenq 的回复:]
这也是常见的问题了
一般设置两个指针p1,p2
首先p1和p2都指向head
然后p2向前走n步，这样p1和p2之间就间隔n个节点
然后p1和p2同时向前步进，当p2到达最后一个节点时，p1就是倒数第n个节点了
[/Quote]

sealedelf 2010-05-26

打赏
举报

Bao同学的博客地址，最近似乎没怎么更新：

http://www.cnblogs.com/Jax/archive/2009/12/11/1621504.html

sealedelf 2010-05-26

打赏
举报

巧了，今天我去面试一个嵌入式职位也考到了这个题，题目可能稍有出入，要求倒数n个的值而已，反正我是用的笨办法，递归遍历把所有元素装到一个数组里，然后直接拿倒数第n个元素，貌似杯具了。

刚才google到了一个真正一次遍历的算法，虽然是C#写的，改写成C/C++也没什么难，来自Jianqiang Bao同学的博客。推荐最近要面试的同学都去看看，其它的题目也很好，Jianqiang Bao同学还很贴心的画出了一些图示。总之思路挺清晰，值得我学习。

http://www.cnblogs.com/Jax/archive/2009/12/11/1621504.html

2.找出单链表的倒数第4个元素

这道题目有两种算法，但无论哪种算法，都要考虑单链表少于4个元素的情况：

第1种算法，建立两个指针，第一个先走4步，然后第2个指针也开始走，两个指针步伐（前进速度）一致。

第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];
}

本题目源代码下载：

推而广之，对倒数第K个元素，都能用以上2种算法找出来。

xhp7185 2010-05-04

打赏
举报

学习了啊

javaaaaaaa 2010-04-29

打赏
举报



node fun(node* head, int k){

     

     node* ret=NULL;



     recurFind(head,k,ret);



     return ret;

    



}



int recurFind(node* head,int k, node* &ret){

    int pos=(head==NULL?0:1+recurFind(head->next,k,ret));

    if(pos==k){

        ret=head;

    }

    return pos;





}

xiaofengfengliu 2010-04-28

打赏
举报

node *p1,*p2;
p1=p2=head;int sum=0;
while(p1) //节点个数
{
sum++;p1=p1->next;
}
while(p2)
{
for(int i=0;i<=(sum-index);i++)
{
p2=p2->next;
}
}
return *p2;

ly_littlefish 2010-04-28

打赏
举报

[Quote=引用 5 楼 xuwenq 的回复:]
这也是常见的问题了
一般设置两个指针p1,p2
首先p1和p2都指向head
然后p2向前走n步，这样p1和p2之间就间隔n个节点
然后p1和p2同时向前步进，当p2到达最后一个节点时，p1就是倒数第n个节点了
[/Quote]

膜拜学习~~~~~

zy2027396 2010-04-19

打赏
举报

顶了学习ing

sunshine0730vip 2010-04-16

打赏
举报

我认真学习了!

zhxi55 2010-04-16

打赏
举报

T t = List<T>.ToArray()[Length - n];

wangguyue86 2010-04-16

打赏
举报

双指针是最好的办法如果想不到的话起码能想到压栈吧

wangguyue86 2010-04-16

打赏
举报

[Quote=引用 100 楼 jxgzlxj 的回复:]

引用 5 楼 xuwenq 的回复:
这也是常见的问题了
一般设置两个指针p1,p2
首先p1和p2都指向head
然后p2向前走n步，这样p1和p2之间就间隔n个节点
然后p1和p2同时向前步进，当p2到达最后一个节点时，p1就是倒数第n个节点了

你这有个问题，就是当n大于整个表长的一半时这种算法不管用了。
[/Quote]

为什么

liufuyahong 2010-04-16

打赏
举报



node fun(node* head, int index)

{

   int i=0;

   node* pNode = head;

   node* buffer[index];

   memset(buffer,NULL,index);   



   while ( pNode != NULL){     

     buffer[i % index] = pNode ;

     pNode = pNode -> next;



     i++; 

   }

   if( i < index )

    return NULL;

   

   return (*buffer[(i - index) % index]);

}