Chinaunix首页 | 论坛 | 博客
  • 博客访问: 580798
  • 博文数量: 192
  • 博客积分: 3780
  • 博客等级: 中校
  • 技术积分: 1487
  • 用 户 组: 普通用户
  • 注册时间: 2010-08-26 10:11
文章存档

2012年(6)

2011年(160)

2010年(26)

分类: C/C++

2011-09-11 11:28:14

腾讯的一道链表笔试题    

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

 

对于这个问题属于常见的问题了
一般设置两个指针p1,p2
首先p1和p2都指向head
然后p2向前走n步,这样p1和p2之间就间隔n个节点
然后p1和p2同时向前步进,当p2到达最后一个节点时,p1就是倒数第n个节点了

下面给出个例子来进一步说明

node fun(node * head, int index)
{
    node
*ptr1,*ptr2;
   
int i = 0;
    ptr1
= head;
    ptr2
= head;
   
if( head == NULL || head->next == NULL )
       
return ptr1;
   
   
while(i<index)   //保证向后移动index个位置
    {
        ptr1
= ptr1->next;
       
if(ptr1 == NULL)
           
return head;
        i
++;
    }

   
while(ptr1->next != NULL)
    {
        ptr1
= ptr1->next;
        ptr2
= ptr2->next;
    }

   
return *ptr2;
}

 

除了上面的方法,还有另外的方法,

一、整个static count 第一次遍历时求出 链的总长,第二次开始直接步进count-index

缺点:进行了两遍遍历。

二、将链表倒置。其实也不是很好。

 

http://zjf30366.blog.163.com/blog/static/4111645820103159470862/

阅读(524) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~