腾讯的一道链表笔试题「总结」

腾讯的一道链表笔试题「总结」

出题的大致函数声明：
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 {
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

缺点：进行了两遍遍历。

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

【腾讯的一道链表笔试题「总结」】相关文章：

一道腾讯的面试题07-09

关于腾讯笔试题07-10

tencent腾讯 笔试题07-10

关于腾讯技术类笔试题07-10

跪求腾讯前端面试题07-10

腾讯实习生笔试题 网页重构07-10

华为笔试题硬件笔经07-11

软件工程师笔试题目11-腾讯07-10

腾讯技术类校园招聘笔试试题(A8卷)07-12

一道Java面试题，题目如下07-11