找出链表倒数第n个节点元素的二个方法
本文提供了找出链表倒数第n个节点元素的二个方法，其中一个方法是JAVA代码实现
方法一：利用两个指针p,q，首先将q往链表尾部移动n位，然后再将p、q一起往后移，那么当q达到链表尾部时，p即指向链表的倒数第n个节点。
node* find_nth_to_last(node* head,int n) { if(head==NULL || n<1) return NULL; node*p,*q; p=q=head; while(q!=NULL && n--){ q=q->next; } if(n>=0) return NULL; while(p!=NULL && q!=NULL){ p=p->next; q=q->next; } return p; }
方法二:可以先计算出节点个数,即从头到尾遍历一次链表,得到个数m,那么倒数第n个元素也即第m-n+1个元素.与方法一是同样的思维,只是具体操作方式不同,代码略.
JAVA代码:
LinkedListNode nthToLast(LinkedListNode head, int n) { if (head == null || n < 1) { return null; } LinkedListNode p1 = head; LinkedListNode p2 = head; for (int j = 0; j < n - 1; ++j) { // skip n-1 steps ahead if (p2 == null) { return null; // not found since list size < n } p2 = p2.next; } while (p2.next != null) { p1 = p1.next; p2 = p2.next; } return p1; }
代码如下:
node* find_nth_to_last(node* head,int n) { if(head==NULL || n<1) return NULL; node*p,*q; p=q=head; while(q!=NULL && n--){ q=q->next; } if(n>=0) return NULL; while(p!=NULL && q!=NULL){ p=p->next; q=q->next; } return p; }
方法二:可以先计算出节点个数,即从头到尾遍历一次链表,得到个数m,那么倒数第n个元素也即第m-n+1个元素.与方法一是同样的思维,只是具体操作方式不同,代码略.
JAVA代码:
代码如下:
LinkedListNode nthToLast(LinkedListNode head, int n) { if (head == null || n < 1) { return null; } LinkedListNode p1 = head; LinkedListNode p2 = head; for (int j = 0; j < n - 1; ++j) { // skip n-1 steps ahead if (p2 == null) { return null; // not found since list size < n } p2 = p2.next; } while (p2.next != null) { p1 = p1.next; p2 = p2.next; } return p1; }
收藏文章
热评话题
- Android定时器实现的几种方式整理及removeCallbacks失效问题解决_Android开发_龙盟编程网
- 在ASP.Net中应用Javascript_Javascript编程_龙盟编程网
- 查询反向链接中link和domain的区别_SEO优化_龙盟编程网
- sql 查询本年、本月、本日记录的语句,附SQL日期函数_Sql Server开发_龙盟编程网
- 在linux中导入sql文件的方法分享(使用命令行转移mysql数据库)_MySQL 技术_龙盟编程网
- 如何应用PHP函数imagettftext处理图片_php编程_个人技术分享
- 如何解决C语言,函数名与宏冲突_C/C++开发_龙盟编程网
精彩图集
精彩文章
