[導(dǎo)讀]新手必看！
—————? 第二天? —————
什么意思呢？我們以下面這個鏈表為例：
給定鏈表的頭結(jié)點，但并不知道鏈表的實際長度，要求我們找到鏈表的倒數(shù)第n個結(jié)點。
假設(shè)n=3，那么要尋找的結(jié)點就是元素1：
如何利用隊列呢？小灰的思路如下：
1.創(chuàng)建一個長度為n的隊列，遍歷原始鏈表，讓結(jié)點逐一進入隊列：
2.當(dāng)隊列已滿時，讓隊尾元素出隊，新結(jié)點入隊：
3.當(dāng)鏈表全部結(jié)點遍歷完畢時，隊尾的元素就是倒數(shù)第n個結(jié)點（因為隊列長度是n）：
————————————
首先，我們創(chuàng)建兩個指針P1和P2，P1指向鏈表的頭結(jié)點，P2指向鏈表的正數(shù)第n個結(jié)點（也就是例子中的第3個結(jié)點）：
接下來，我們讓指針P1和P2同時循環(huán)右移，每次右移一步，直到指針P2移動到鏈表的末尾：
此時，由于P2指向鏈表的尾結(jié)點，且P1和P2的距離是n-1，因此P1所指的結(jié)點就是我們要尋找的鏈表倒數(shù)第n個結(jié)點：
顯然，這個方法從頭到尾只需要對鏈表做一次遍歷，而且僅僅使用了兩個指針，算法的空間復(fù)雜度是O（1）。
public?class?NthFromEnd?{
????public?static?Node?findNthFromEnd(Node?head,?int?n){
????????Node?p1?=?head;
????????Node?p2?=?head;
????????//把p2指針移動到正數(shù)第n個結(jié)點
????????for(int?i=1;?i????????????p2?=?p2.next;
????????????if(p2?==?null){
????????????????throw?new?IllegalArgumentException("參數(shù)n超出鏈表長度！");
????????????}
????????}
????????//p1和p2一起右移，直到p2指向鏈表尾結(jié)點
????????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é)點
????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個元素是："?+?node.data);
????}
}
—————END—————
喜歡本文的朋友，歡迎關(guān)注公眾號?程序員小灰，收看更多精彩內(nèi)容
點個[在看]，是對小灰最大的支持！
免責(zé)聲明：本文內(nèi)容由21ic獲得授權(quán)后發(fā)布，版權(quán)歸原作者所有，本平臺僅提供信息存儲服務(wù)。文章僅代表作者個人觀點，不代表本平臺立場，如有問題，請聯(lián)系我們，謝謝！
下載文檔
