怎么找到链表的倒数第n个结点
本篇内容主要讲解“怎么找到链表的倒数第n个结点”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“怎么找到链表的倒数第n个结点”吧!
创新互联建站专注为客户提供全方位的互联网综合服务,包含不限于成都做网站、成都网站建设、绵竹网络推广、微信小程序开发、绵竹网络营销、绵竹企业策划、绵竹品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等,从售前售中售后,我们都将竭诚为您服务,您的肯定,是我们最大的嘉奖;创新互联建站为所有大学生创业者提供绵竹建站搭建服务,24小时服务热线:18980820575,官方网址:www.cdcxhl.com
什么意思呢?我们以下面这个链表为例:
给定链表的头结点,但并不知道链表的实际长度,要求我们找到链表的倒数第n个结点。
假设n=3,那么要寻找的结点就是元素1:
如何利用队列呢?小灰的思路如下:
1.创建一个长度为n的队列,遍历原始链表,让结点逐一进入队列:
2.当队列已满时,让队尾元素出队,新结点入队:
3.当链表全部结点遍历完毕时,队尾的元素就是倒数第n个结点(因为队列长度是n):
————————————
首先,我们创建两个指针P1和P2,P1指向链表的头结点,P2指向链表的正数第n个结点(也就是例子中的第3个结点):
接下来,我们让指针P1和P2同时循环右移,每次右移一步,直到指针P2移动到链表的末尾:
此时,由于P2指向链表的尾结点,且P1和P2的距离是n-1,因此P1所指的结点就是我们要寻找的链表倒数第n个结点:
显然,这个方法从头到尾只需要对链表做一次遍历,而且仅仅使用了两个指针,算法的空间复杂度是O(1)。
public class NthFromEnd { public static Node findNthFromEnd(Node head, int n){ Node p1 = head; Node p2 = head; //把p2指针移动到正数第n个结点 for(int i=1; i到此,相信大家对“怎么找到链表的倒数第n个结点”有了更深的了解,不妨来实际操作一番吧!这里是创新互联网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!
文章题目:怎么找到链表的倒数第n个结点
分享链接:http://scyanting.com/article/ieoscj.html