面试题:用Java逆序打印链表

昨天的 Java 实现单例模式中，我们的双重检验锁机制因为指令重排序问题而引入了 volatile 关键字，不少朋友问我，到底为啥要加 volatile 这个关键字呀，而它，到底又有什么神奇的作用呢？

创新互联专注为客户提供全方位的互联网综合服务，包含不限于成都做网站、成都网站制作、成都外贸网站建设、正镶白网络推广、小程序开发、正镶白网络营销、正镶白企业策划、正镶白品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等，从售前售中售后，我们都将竭诚为您服务，您的肯定，是我们最大的嘉奖；创新互联为所有大学生创业者提供正镶白建站搭建服务，24小时服务热线：13518219792，官方网址：www.cdcxhl.com

对 volatile 这个关键字，在昨天的讲解中我们简单说了一下：被 volatile 修饰的共享变量，都会具有下面两个属性：

保证不同线程对该变量操作的内存可见性。
禁止指令重排序。

共享变量：如果一个变量在多个线程的工作内存中都存在副本，那么这个变量就是这几个线程的共享变量。

可见性：一个线程对共享变量值的修改，能够及时地被其它线程看到。

对于重排序，不熟悉的建议直接 Google 一下，这里也就不多提了。只需要记住，在多线程中操作一个共享变量的时候，一定要记住加上 volatile 修饰即可。

由于时间关系，我们还是得先进入今天的正题，对于 volatile 关键字，在要求并发编程能力的面试中还是很容易考察到的，后面我也会简单给大家讲解。

输入一个单链表的头结点，从尾到头打印出每个结点的值。

我们的链表有很多，单链表，双向链表，环链表等。这里是最普通的单链表模式，我们一般会在数据存储区域存放数据，然后有一个指针指向下一个结点。虽然 Java 中没有指针这个概念，但 Java 的引用恰如其分的填补了这个问题。

看到这道题，我们往往会很快反应到每个结点都有 next 属性，所以要从头到尾输出很简单。于是我们自然而然就会想到先用一个 while 循环取出所有的结点存放到数组中，然后再通过逆序遍历这个数组，即可实现逆序打印单链表的结点值。

我们假定结点的数据为 int 型的。实现代码如下：

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

  public static void printLinkReverse(Node head) {
    ArrayList 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);
  }
}

这样的方式确实能实现逆序打印链表的数据，但明显用了整整两次循环，时间复杂度为 O(n²)。等等！逆序输出？似乎有这样一个数据结构可以完美解决这个问题，这个数据结构就是栈。

栈是一种「后进先出」的数据结构，用栈的原理更好能达到我们的要求，于是实现代码如下：

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

  public static void printLinkReverse(Node head) {
    Stack 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);
  }
}

既然可以用栈来实现，我们也极容易想到递归也能解决这个问题，因为递归本质上也就是一个栈结构。要实现逆序输出链表，我们每访问一个结点的时候，我们先递归输出它后面的结点，再输出该结点本身，这样链表的输出结果自然也是反过来了。

代码如下：

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);
  }
}

虽然递归代码看起来确实很整洁，但有个问题：当链表非常长的时候，一定会导致函数调用的层级很深，从而有可能导致函数调用栈溢出。所以显示用栈基于循环实现的代码，健壮性还是要好一些的。

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持创新互联。

名称栏目：面试题:用Java逆序打印链表
本文路径：http://myzitong.com/article/gdjcoj.html

面试题:用Java逆序打印链表

其他资讯