[[347134]]

 

————— 第二天 —————

 

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

 

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

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

 

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

1.創建一個長度為n的隊列，遍歷原始鏈表，讓結點逐一進入隊列：

 

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

 

3.當鏈表全部結點遍歷完畢時，隊尾的元素就是倒數第n個結點(因為隊列長度是n)：

 

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

 

首先，我們創建兩個指針P1和P2，P1指向鏈表的頭結點，P2指向鏈表的正數第n個結點(也就是例子中的第3個結點)：

 

接下來，我們讓指針P1和P2同時循環右移，每次右移一步，直到指針P2移動到鏈表的末尾：

 

此時，由于P2指向鏈表的尾結點，且P1和P2的距離是n-1，因此P1所指的結點就是我們要尋找的鏈表倒數第n個結點：

 

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

 

 

public class NthFromEnd { 
    public static Node findNthFromEnd(Node head, int n){ 
        Node p1 = head; 
        Node p2 = head; 
        //把p2指針移動到正數第n個結點 
        for(int i=1; i<n; i++){ 
            p2 = p2.next; 
            if(p2 == null){ 
                throw new IllegalArgumentException("參數n超出鏈表長度！"); 
            } 
        } 
        //p1和p2一起右移，直到p2指向鏈表尾結點 
        while (p2.next != null){ 
            p1 = p1.next; 
            p2 = p2.next; 
        } 
        return p1; 
    } 
 
    //快速創建鏈表 
    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; 
    } 
 
    //鏈表節點 
    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("鏈表倒數第3個元素是：" + node.data); 
    } 
 
} 

本文轉載自微信公眾號「程序員小灰」，可以通過以下二維碼關注。轉載本文請聯系程序員小灰公眾號。