查找单链表中倒数第n个节点

单链表操作练习
服务器君一共花费了332.883 ms进行了6次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

通过一次遍历找到单链表中倒数第n个节点,链表可能相当大,可使用辅助空间,但是辅助空间的数目必须固定,不能和n有关。

单向链表的特点是遍历到末尾后不能反向重数N个节点。因此必须在到达尾部的同时找到倒数第N个节点。

不管是顺数n个还是倒数n个,其实都是距离-标尺问题。标尺是一段距离可以用线段的两个端点来衡量,我们能够判断倒数第一个节点,因为他的next==NULL。如果我们用两个指针,并保持他们的距离为n,那么当这个线段的右端指向末尾节点时,左端节点就指向倒数第n个节点。

iNode * GetLastNnode(iNode * head, int n)
{
	iNode * pfirst=head;
	iNode *psecond=head;
       
	int counter;
    //第1步:建立标尺,移动pfirst N步
	for(counter=0; counter<n; counter++) 
    {
    	if((NULL == pfirst)
      	break; // 此时pfirst->next无意义
      	pfirst=pfirst->next;
	}
       
 	if(n != counter) //长度不够n,未找到倒数第n个节点
    	return NULL;
 
	//第2步:保持距离让标尺向右移动,直到右端指向末尾,左端即结果
	while(pfirst!=NULL) 
    {
		pfirst=pfirst->next;
   		psecond=psecond->next;
	}
 	return psecond;
}
 
 
iNode * GetLastNnode ( iNode *head, int n)
{
    iNode * pfirst = head;
    iNode * psecond = NULL;//可能没有n个
    while( n-- > 0 && (pfirst!= NULL)
    {
        pfirst = pfirst ->next;
	}
 
    if(pfirst!= NULL)// 有n个节点
        psecond = head;
 
    while(pfirst!=NULL)
    {
         pfirst = pfirst ->next;
         psecond = psecond ->next;
    }
    return psecond; //只有一个出口,无论是否有n个节点,都能返回正确值
}

一次遍历单向链表找到中间节点

和上面的思路类似,设置2个指针,一个走2步时,另一个走1步。那么一个走到头时,另一个走到中间。

iNode * GetMiddleNode ( iNode *head )
{
    iNode *p1 = head;
    iNode *p2 = p1;
    while( p2 )
    {
        p2 = p2->next;
        if(p2)
        {
            p2 = p2->next;
            p1=p1->next;
        }
    }
    return p1;
}

本文地址:http://www.nowamagic.net/librarys/veda/detail/496,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/496

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《代码大全(第2版)》 史蒂夫•迈克康奈尔 (Steve McConnell) (作者), 金戈 (译者)

代码大全(第2版)是著名IT畅销书作者、《IEEE Software》杂志前主编、具有20年编程与项目管理经验的Steve McConnell十余年前的经典著作的全新演绎:第2版做了全面的更新,增加了很多与时俱进的内容,包括对新语言、新的开发过程与方法论的讨论等等。这是一本百科全书式的软件构建手册,涵盖了软件构建活动的方方面面,尤其强调提高软件质量的种种实践方法。

更多计算机宝库...