日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

在龍巖等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場(chǎng)前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供網(wǎng)站設(shè)計(jì)、成都做網(wǎng)站 網(wǎng)站設(shè)計(jì)制作按需設(shè)計(jì)網(wǎng)站,公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),品牌網(wǎng)站設(shè)計(jì),成都營(yíng)銷網(wǎng)站建設(shè),成都外貿(mào)網(wǎng)站建設(shè)公司,龍巖網(wǎng)站建設(shè)費(fèi)用合理。

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

什么意思呢?我們以下面這個(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))：

接下來，我們讓指針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); 
  
  
  
  
    } 
  
  
  
  
 
  
  
  
  
} 
 
 
 
 

本文轉(zhuǎn)載自微信公眾號(hào)「程序員小灰」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系程序員小灰公眾號(hào)。

當(dāng)前文章：漫畫：如何找到鏈表的倒數(shù)第n個(gè)結(jié)點(diǎn)？
分享地址：http://www.dlmjj.cn/article/ccchdcp.html