快捷導(dǎo)航

面試題:用 Java 逆序打印鏈表

更新時(shí)間：2018年07月04日 10:29:56 作者：nanchen2251

這篇文章主要介紹了面試題:用 Java 逆序打印鏈表，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧

昨天的 Java 實(shí)現(xiàn)單例模式中，我們的雙重檢驗(yàn)鎖機(jī)制因?yàn)橹噶钪嘏判騿?wèn)題而引入了 volatile 關(guān)鍵字，不少朋友問(wèn)我，到底為啥要加 volatile 這個(gè)關(guān)鍵字呀，而它，到底又有什么神奇的作用呢？

對(duì) volatile 這個(gè)關(guān)鍵字，在昨天的講解中我們簡(jiǎn)單說(shuō)了一下：被 volatile 修飾的共享變量，都會(huì)具有下面兩個(gè)屬性：

保證不同線(xiàn)程對(duì)該變量操作的內(nèi)存可見(jiàn)性。
禁止指令重排序。

共享變量：如果一個(gè)變量在多個(gè)線(xiàn)程的工作內(nèi)存中都存在副本，那么這個(gè)變量就是這幾個(gè)線(xiàn)程的共享變量。

可見(jiàn)性：一個(gè)線(xiàn)程對(duì)共享變量值的修改，能夠及時(shí)地被其它線(xiàn)程看到。

對(duì)于重排序，不熟悉的建議直接 Google 一下，這里也就不多提了。只需要記住，在多線(xiàn)程中操作一個(gè)共享變量的時(shí)候，一定要記住加上 volatile 修飾即可。

由于時(shí)間關(guān)系，我們還是得先進(jìn)入今天的正題，對(duì)于 volatile 關(guān)鍵字，在要求并發(fā)編程能力的面試中還是很容易考察到的，后面我也會(huì)簡(jiǎn)單給大家講解。

輸入一個(gè)單鏈表的頭結(jié)點(diǎn)，從尾到頭打印出每個(gè)結(jié)點(diǎn)的值。

我們的鏈表有很多，單鏈表，雙向鏈表，環(huán)鏈表等。這里是最普通的單鏈表模式，我們一般會(huì)在數(shù)據(jù)存儲(chǔ)區(qū)域存放數(shù)據(jù)，然后有一個(gè)指針指向下一個(gè)結(jié)點(diǎn)。雖然 Java 中沒(méi)有指針這個(gè)概念，但 Java 的引用恰如其分的填補(bǔ)了這個(gè)問(wèn)題。

看到這道題，我們往往會(huì)很快反應(yīng)到每個(gè)結(jié)點(diǎn)都有 next 屬性，所以要從頭到尾輸出很簡(jiǎn)單。于是我們自然而然就會(huì)想到先用一個(gè) while 循環(huán)取出所有的結(jié)點(diǎn)存放到數(shù)組中，然后再通過(guò)逆序遍歷這個(gè)數(shù)組，即可實(shí)現(xiàn)逆序打印單鏈表的結(jié)點(diǎn)值。

我們假定結(jié)點(diǎn)的數(shù)據(jù)為 int 型的。實(shí)現(xiàn)代碼如下：

public class Test05 {
  public static class Node {
    int data;
    Node next;
  }

  public static void printLinkReverse(Node head) {
    ArrayList<Node> nodes = new ArrayList<>();
    while (head != null) {
      nodes.add(head);
      head = head.next;
    }
    for (int i = nodes.size() - 1; i >= 0; i--) {
      System.out.print(nodes.get(i).data + " ");
    }
  }

  public static void main(String[] args) {
    Node head = new Node();
    head.data = 1;
    head.next = new Node();
    head.next.data = 2;
    head.next.next = new Node();
    head.next.next.data = 3;
    head.next.next.next = new Node();
    head.next.next.next.data = 4;
    head.next.next.next.next = new Node();
    head.next.next.next.next.data = 5;
    printLinkReverse(head);
  }
}

這樣的方式確實(shí)能實(shí)現(xiàn)逆序打印鏈表的數(shù)據(jù)，但明顯用了整整兩次循環(huán)，時(shí)間復(fù)雜度為 O(n²)。等等！逆序輸出？似乎有這樣一個(gè)數(shù)據(jù)結(jié)構(gòu)可以完美解決這個(gè)問(wèn)題，這個(gè)數(shù)據(jù)結(jié)構(gòu)就是棧。

棧是一種「后進(jìn)先出」的數(shù)據(jù)結(jié)構(gòu)，用棧的原理更好能達(dá)到我們的要求，于是實(shí)現(xiàn)代碼如下：

public class Test05 {
  public static class Node {
    int data;
    Node next;
  }

  public static void printLinkReverse(Node head) {
    Stack<Node> stack = new Stack<>();
    while (head != null) {
      stack.push(head);
      head = head.next;
    }
    while (!stack.isEmpty()) {
      System.out.print(stack.pop().data + " ");
    }
  }

  public static void main(String[] args) {
    Node head = new Node();
    head.data = 1;
    head.next = new Node();
    head.next.data = 2;
    head.next.next = new Node();
    head.next.next.data = 3;
    head.next.next.next = new Node();
    head.next.next.next.data = 4;
    head.next.next.next.next = new Node();
    head.next.next.next.next.data = 5;
    printLinkReverse(head);
  }
}

既然可以用棧來(lái)實(shí)現(xiàn)，我們也極容易想到遞歸也能解決這個(gè)問(wèn)題，因?yàn)檫f歸本質(zhì)上也就是一個(gè)棧結(jié)構(gòu)。要實(shí)現(xiàn)逆序輸出鏈表，我們每訪(fǎng)問(wèn)一個(gè)結(jié)點(diǎn)的時(shí)候，我們先遞歸輸出它后面的結(jié)點(diǎn)，再輸出該結(jié)點(diǎn)本身，這樣鏈表的輸出結(jié)果自然也是反過(guò)來(lái)了。

代碼如下：

public class Test05 {
  public static class Node {
    int data;
    Node next;
  }

  public static void printLinkReverse(Node head) {
    if (head != null) {
      printLinkReverse(head.next);
      System.out.print(head.data+" ");
    }
  }

  public static void main(String[] args) {
    Node head = new Node();
    head.data = 1;
    head.next = new Node();
    head.next.data = 2;
    head.next.next = new Node();
    head.next.next.data = 3;
    head.next.next.next = new Node();
    head.next.next.next.data = 4;
    head.next.next.next.next = new Node();
    head.next.next.next.next.data = 5;
    printLinkReverse(head);
  }
}

雖然遞歸代碼看起來(lái)確實(shí)很整潔，但有個(gè)問(wèn)題：當(dāng)鏈表非常長(zhǎng)的時(shí)候，一定會(huì)導(dǎo)致函數(shù)調(diào)用的層級(jí)很深，從而有可能導(dǎo)致函數(shù)調(diào)用棧溢出。所以顯示用?；谘h(huán)實(shí)現(xiàn)的代碼，健壯性還是要好一些的。

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: