【算法】漫畫(huà)：如何找到鏈表的倒數(shù)第n個(gè)結(jié)點(diǎn)？
—————? 第二天? —————
什么意思呢？我們以下面這個(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????????????p2?=?p2.next;
????????????if(p2?==?null){
????????????????throw?new?IllegalArgumentException("參數(shù)n超出鏈表長(zhǎng)度！");
????????????}
????????}
????????//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—————
往期精彩回顧