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

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

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<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²)。等等!逆序输出?似乎有这样一个数据结构可以完美解决这个问题,这个数据结构就是栈。

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

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

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

代码如下:

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

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

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

(0)

相关推荐

  • 基于python实现从尾到头打印链表

    这篇文章主要介绍了基于python实现从尾到头打印链表,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 题目描述 输入一个链表,按链表从尾到头的顺序返回一个ArrayList. 思路 遍历链表,把结构保存在list里面,然后把list逆序输出 代码 # -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None

  • Python3实现的判断回文链表算法示例

    本文实例讲述了Python3实现的判断回文链表算法.分享给大家供大家参考,具体如下: 问题: 请判断一个链表是否为回文链表. 方案一:指针法 class Solution: def isPalindrome(self, head): """ 判断一个链表是否是回文的,很自然的想法就是两个指针,一个指针从前往后走,一个指针从后往前走,判断元素值是否相同,这里要分几个步骤来进行求解: 1.找到链表长度的一半,用追赶法,一个指针一次走两步,一个指针一次走一步 2.将后一半数组转置

  • c语言链表基本操作(带有创建链表 删除 打印 插入)

    复制代码 代码如下: #include <stdio.h>#include <stdlib.h>#include <malloc.h>#define LEN sizeof(struct Student)struct Student{    long num;    float score;    struct Student*next;};int n;int main(){    /*-----------------------------程序描述----------

  • 对python实现合并两个排序链表的方法详解

    输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则. 1.迭代方法 def Merge(self, pHead1, pHead2): p1, p2 = pHead1, pHead2 if p1 and p2: if p1.val < p2.val: head = p1 p1 = p1.next else: head = p2 p2 = p2.next cur = head elif p1: return p1 else: return p2 while p

  • C++实现打印两个有序链表公共部分的方法

    本文实例讲述了C++实现打印两个有序链表公共部分的方法.分享给大家供大家参考,具体如下: 题目: 给定两个有序链表的头指针head1和head2,打印两个链表的公共部分. 解题思路及代码: 1.head1的值小于head2,则head1往下移动 2.head1的值小于head2,则head2往下移动 3.相等则打印任何一个链表节点的值,head1和head2都往下移动. 4.当head1或head2移动到NULL,终止. 算法C++代码: typedef struct Node { int da

  • Java编程实现从尾到头打印链表代码实例

    问题描述:输入一个链表的头结点,从尾巴到头反过来打印出每个结点的值. 首先定义链表结点 public class ListNode { int val; ListNode next = null; ListNode(int val){ this.val = val; } } 思路1:此题明显想到是利用栈的思想,后进先出,先遍历链表,依次将结点值进栈.最后在遍历栈出栈. public static Stack<Integer> printListReverse_Stack(ListNode li

  • PHP从尾到头打印链表实例讲解

    题目 输入一个链表,从尾到头打印链表每个节点的值. 题解 一种是使用栈. 第二种是递归. 代码 //递归版本 function printListFromTailToHead($head) { if($head == NULL){ return []; } $arr = array(); $cur = $head; if($cur->next != null){ $arr = printListFromTailToHead($cur->next); } array_push($arr, $cu

  • python算法题 链表反转

    链表的反转是一个很常见.很基础的数据结构题,输入一个单向链表,输出逆序反转后的链表,如图:上面的链表转换成下面的链表.实现链表反转有两种方式,一种是循环迭代,另外一种方式是递归. 第一种方式:循坏迭代 循坏迭代算法需要三个临时变量:pre.head.next,临界条件是链表为None或者链表就只有一个节点. # encoding: utf-8 class Node(object): def __init__(self): self.value = None self.next = None de

  • Python实现合并两个有序链表的方法示例

    本文实例讲述了Python实现合并两个有序链表的方法.分享给大家供大家参考,具体如下: 思路:先选出第一个节点,然后遍历两个链表,把小的作为当前节点的下一个节点,一直到其中一个链表遍历完,这时候把另一个链表直接接上就好 # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(obj

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

    昨天的 Java 实现单例模式 中,我们的双重检验锁机制因为指令重排序问题而引入了 volatile 关键字,不少朋友问我,到底为啥要加 volatile 这个关键字呀,而它,到底又有什么神奇的作用呢? 对 volatile 这个关键字,在昨天的讲解中我们简单说了一下:被 volatile 修饰的共享变量,都会具有下面两个属性: 保证不同线程对该变量操作的内存可见性. 禁止指令重排序. 共享变量:如果一个变量在多个线程的工作内存中都存在副本,那么这个变量就是这几个线程的共享变量. 可见性:一个线

  • Java根据正整数的位数并逆序打印出各位数字

    题目:给一个不多于5位的正整数,要求:一.求它是几位数,二.逆序打印出各位数字. 程序设计: import java.util.Scanner; public class Ex24 { public static void main(String[] args) { Ex24 tn = new Ex24(); Scanner s = new Scanner(System.in); long a = s.nextLong(); if(a < 0 || a > 100000) { System.o

  • python逆序打印各位数字的方法

    如下所示: # -*- coding: utf-8 -*- # raw_input获取给定的一个不多于5位的正整数. # 一.求它是几位数: # 二.逆序打印出各位数字. def f(n): m = map(int, n) print "该数为%d位数"%len(m) m.reverse() for i in m: print i, if __name__=="__main__": n=raw_input("请输入一个多位数的正整数:") f(n

  • Java实现单链表SingleLinkedList增删改查及反转 逆序等

    节点类 可以根据需要,对节点属性进行修改.注意重写toString()方法,以便后续的输出操作. //节点类 class Node { public int id; public String name; public Node next; public Node(int id, String name) { this.id = id; this.name = name; } @Override public String toString() { return "Node{" + &

  • Java数据结构之单链表的实现与面试题汇总

    目录 1 单链表 1.1 单链表介绍 1.2 单链表的实现思路分析 1.3 实现代码 2 单链表的面试题 2.1 统计单链表中有效节点数量 2.2 新浪–倒数第k个节点 2.3 腾讯–单链表的反转 2.4 百度–逆序打印单链表 1 单链表 1.1 单链表介绍 由于顺序表的插入删除操作需要移动大量的元素,影响了运行效率,因此引入了线性表的链式存储——单链表.单链表通过一组任意的存储单元来存储线性表中的数据元素,不需要使用地址连续的存储单元,因此它 不要求在逻辑上相邻的两个元素在物理位置上也相邻.

  • C/C++ 双链表之逆序的实例详解

    C/C++ 双链表之逆序的实例详解 一.结点结构 双向链表的数据结构定义如下: typedef struct node { ElemType data; struct node *prior struct node *next; }list; 其中,ElemType可以是任意数据类型如int.float或者char等,在算法中,规定其默认为int类型. 二.带头结点 本文描述的是双向链表逆序,链表逆序需要维护3个指针,分别指向前一个节点.当前节点和下一个节点,具体代码如下: list *reve

  • C语言 分析逆序字符串与字符串的逆序输出有什么区别

    目录 前言 一.字符串的逆序 二.实例讲解 1.字符串的逆序输出 2.逆序字符串 3.综合实例 总结 今天我们讲解字符串的逆序和逆序输出,并且通过一个综合题型来加深印象和练手! 前言 逆序字符串和字符串的逆序输出,可能经常会有人混淆,所以今天带大家一起来看一看吧! 一.字符串的逆序 字符串的逆序输出是什么? 逆序字符串:针对一个输入的字符串数组,通过逆序,将其数组内容进行翻转逆序. 字符串的逆序输出:对于一个字符串,只需要数组创建,然后求出字符串的长度,从字符串数组最后一个元素依次输出,直到第一

  • C语言指针如何实现字符串逆序反转

    目录 指针实现字符串逆序反转 知识点 字符串逆序的几种写法 非递归写法 递归写法 指针实现字符串逆序反转 #include<stdio.h> #include<string.h> void rec(char* arr) { //int len = sizeof(arr); // 判断字符串长度需要用strlen. int len = strlen(arr); printf("字符串长度len = %d\n", len); char* p1 = arr; char

  • java实现单链表之逆序

    下面一段代码准确的介绍了java实现单链表逆序,具体内容就不做详解了,有需要的朋友可以直接拷贝了 package com.ckw.mianshi; /** * java 实现单链表的逆序 * @author Administrator * */ public class SingleLinkedReverse { class Node{ int data; Node next; public Node(int data){ this.data = data; } } public static

  • java单链表逆序用法代码示例

    本篇博客,比较简单.对单链表逆序不理解的看看就可以了. 逆序思想 现假设有一链表,有待逆序操作.我们首先想到的就是将那个指针关系逆序了就行了呗. 事实上,就是这样.博主就是以这个为目标来完成的单链表逆序操作. Node pre = null; Node post = null; while(head!=null){ post = head.next; head.next = pre; pre = head; head = post; } 这便是逆序的核心了.下面我们就来一步步的讲解. 首次逆序:

随机推荐