腾讯的一道链表笔试题“总结”
出题的大致函数声明:
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
缺点:进行了两遍遍历。
二、将链表倒置。其实也不是很好。
-
假期总结优秀范文
总结是在一段时间内对学习和工作生活等表现加以总结和概括的一种书面材料,它能够使头脑更加清醒,目标更加明确,是时候写一份总结了。那么如何把总结写出新花样呢?下面是小编帮大家整理的假期总结优秀范文,欢迎阅读,希望大家能够喜欢。假期总结优秀范文1在现今社会,就...
-
(通用)工程部经理年终工作总结
总结就是把一个时间段取得的成绩、存在的问题及得到的经验和教训进行一次全面系统的总结的书面材料,它是增长才干的一种好办法,让我们一起来学习写总结吧。总结怎么写才能发挥它的作用呢?以下是小编精心整理的工程部经理年终工作总结,希望对大家有所帮助。工程部经...
-
收银员个人年终工作总结大全
总结是事后对某一阶段的学习、工作或其完成情况加以回顾和分析的一种书面材料,它可以使我们更有效率,因此我们要做好归纳,写好总结。那么你知道总结如何写吗?下面是小编精心整理的收银员个人年终工作总结大全,希望能够帮助到大家。收银员个人年终工作总结大全1有时...
-
(实用)商场保安个人年终工作总结
总结在一个时期、一个年度、一个阶段对学习和工作生活等情况加以回顾和分析的一种书面材料,它能够使头脑更加清醒,目标更加明确,不妨坐下来好好写写总结吧。总结怎么写才不会流于形式呢?下面是小编收集整理的商场保安个人年终工作总结,希望对大家有所帮助。商场保安...