漫畫：如何找到鏈表的倒數(shù)第n個(gè)結(jié)點(diǎn)？
—————? 第二天? —————
什么意思呢？我們以下面這個(gè)鏈表為例：
給定鏈表的頭結(jié)點(diǎn)，但并不知道鏈表的實(shí)際長度，要求我們找到鏈表的倒數(shù)第n個(gè)結(jié)點(diǎn)。
假設(shè)n=3，那么要尋找的結(jié)點(diǎn)就是元素1：
如何利用隊(duì)列呢？小灰的思路如下：
1.創(chuàng)建一個(gè)長度為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ì)列長度是n）：
————————————
首先，我們創(chuàng)建兩個(gè)指針P1和P2，P1指向鏈表的頭結(jié)點(diǎn)，P2指向鏈表的正數(shù)第n個(gè)結(jié)點(diǎn)（也就是例子中的第3個(gè)結(jié)點(diǎn)）：
接下來，我們讓指針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????????????p2?=?p2.next;
????????????if(p2?==?null){
????????????????throw?new?IllegalArgumentException("參數(shù)n超出鏈表長度！");
????????????}
????????}
????????//p1和p2一起右移，直到p2指向鏈表尾結(jié)點(diǎn)
????????while?(p2.next?!=?null){
????????????p1?=?p1.next;
????????????p2?=?p2.next;
????????}
????????return?p1;
????}
????//快速創(chuàng)建鏈表
????private?static?Node?buildLinkList(int[]?array){
????????Node?head?=?new?Node(array[0]);
????????Node?p?=?head;
????????for(int?i=1;?i????????????p.next?=?new?Node(array[i]);
????????????p?=?p.next;
????????}
????????return?head;
????}
????//鏈表節(jié)點(diǎn)
????private?static?class?Node?{
????????int?data;
????????Node?next;
????????Node(int?data)?{
????????????this.data?=?data;
????????}
????}
????public?static?void?main(String[]?args)?{
????????int[]?inputs?=?{5,3,7,2,4,1,9,8};
????????Node?head?=?buildLinkList(inputs);
????????Node?node?=?findNthFromEnd(head,3);
????????System.out.println("鏈表倒數(shù)第3個(gè)元素是："?+?node.data);
????}
}
—————END—————
喜歡本文的朋友，歡迎關(guān)注公眾號(hào)?程序員小灰，收看更多精彩內(nèi)容
點(diǎn)個(gè)[在看]，是對(duì)小灰最大的支持！
免責(zé)聲明：本文內(nèi)容由21ic獲得授權(quán)后發(fā)布，版權(quán)歸原作者所有，本平臺(tái)僅提供信息存儲(chǔ)服務(wù)。文章僅代表作者個(gè)人觀點(diǎn)，不代表本平臺(tái)立場，如有問題，請聯(lián)系我們，謝謝！
下載文檔
