服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - Java教程 - 面试题:用 Java 逆序打印链表

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

2021-05-13 11:35nanchen2251 Java教程

这篇文章主要介绍了面试题:用 Java 逆序打印链表,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧

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

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

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

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

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

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

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

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

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

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

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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);
  }
}

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

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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);
  }
}

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

代码如下:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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);
  }
}

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

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持服务器之家。

原文链接:https://www.jianshu.com/p/65e4df545410

延伸 · 阅读

精彩推荐