本篇內(nèi)容主要講解“怎么找到鏈表的倒數(shù)第n個(gè)結(jié)點(diǎn)”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“怎么找到鏈表的倒數(shù)第n個(gè)結(jié)點(diǎn)”吧!

創(chuàng)新互聯(lián)建站專注為客戶提供全方位的互聯(lián)網(wǎng)綜合服務(wù)，包含不限于成都做網(wǎng)站、成都網(wǎng)站建設(shè)、綿竹網(wǎng)絡(luò)推廣、微信小程序開(kāi)發(fā)、綿竹網(wǎng)絡(luò)營(yíng)銷、綿竹企業(yè)策劃、綿竹品牌公關(guān)、搜索引擎seo、人物專訪、企業(yè)宣傳片、企業(yè)代運(yùn)營(yíng)等，從售前售中售后，我們都將竭誠(chéng)為您服務(wù)，您的肯定，是我們最大的嘉獎(jiǎng)；創(chuàng)新互聯(lián)建站為所有大學(xué)生創(chuàng)業(yè)者提供綿竹建站搭建服務(wù)，24小時(shí)服務(wù)熱線：18980820575，官方網(wǎng)址：www.cdcxhl.com

什么意思呢?我們以下面這個(gè)鏈表為例：

給定鏈表的頭結(jié)點(diǎn)，但并不知道鏈表的實(shí)際長(zhǎng)度，要求我們找到鏈表的倒數(shù)第n個(gè)結(jié)點(diǎn)。

假設(shè)n=3，那么要尋找的結(jié)點(diǎn)就是元素1：

如何利用隊(duì)列呢?小灰的思路如下：

1.創(chuàng)建一個(gè)長(zhǎng)度為n的隊(duì)列，遍歷原始鏈表，讓結(jié)點(diǎn)逐一進(jìn)入隊(duì)列：

2.當(dāng)隊(duì)列已滿時(shí)，讓隊(duì)尾元素出隊(duì)，新結(jié)點(diǎn)入隊(duì)：

3.當(dāng)鏈表全部結(jié)點(diǎn)遍歷完畢時(shí)，隊(duì)尾的元素就是倒數(shù)第n個(gè)結(jié)點(diǎn)(因?yàn)殛?duì)列長(zhǎng)度是n)：

————————————

首先，我們創(chuàng)建兩個(gè)指針P1和P2，P1指向鏈表的頭結(jié)點(diǎn)，P2指向鏈表的正數(shù)第n個(gè)結(jié)點(diǎn)(也就是例子中的第3個(gè)結(jié)點(diǎn))：

接下來(lái)，我們讓指針P1和P2同時(shí)循環(huán)右移，每次右移一步，直到指針P2移動(dòng)到鏈表的末尾：

此時(shí)，由于P2指向鏈表的尾結(jié)點(diǎn)，且P1和P2的距離是n-1，因此P1所指的結(jié)點(diǎn)就是我們要尋找的鏈表倒數(shù)第n個(gè)結(jié)點(diǎn)：

顯然，這個(gè)方法從頭到尾只需要對(duì)鏈表做一次遍歷，而且僅僅使用了兩個(gè)指針，算法的空間復(fù)雜度是O(1)。

public class NthFromEnd {     public static Node findNthFromEnd(Node head, int n){         Node p1 = head;         Node p2 = head;         //把p2指針移動(dòng)到正數(shù)第n個(gè)結(jié)點(diǎn)         for(int i=1; i
到此，相信大家對(duì)“怎么找到鏈表的倒數(shù)第n個(gè)結(jié)點(diǎn)”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！
            
            
                        

            網(wǎng)站標(biāo)題：怎么找到鏈表的倒數(shù)第n個(gè)結(jié)點(diǎn)            

            分享鏈接：http://weahome.cn/article/ieoscj.html