怎么找到鏈表的倒數(shù)第n個結(jié)點

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

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

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

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

如何利用隊列呢?小灰的思路如下：

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

2.當隊列已滿時，讓隊尾元素出隊，新結(jié)點入隊：

3.當鏈表全部結(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é)點：

顯然，這個方法從頭到尾只需要對鏈表做一次遍歷，而且僅僅使用了兩個指針，算法的空間復雜度是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<n; 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<array.length; 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);     }  }

到此，相信大家對“怎么找到鏈表的倒數(shù)第n個結(jié)點”有了更深的了解，不妨來實際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進入相關(guān)頻道進行查詢，關(guān)注我們，繼續(xù)學習！