做网站更新维护工资高吗/品牌营销策划网站

前言

本博文部分图片, 思路来自于剑指offer 或者编程珠玑

问题描述

思路

书中给出的思路有两种
思路一 : 利用额外的一个栈维护链表中的数据, 然后在逐个出栈即可

思路二 : 递归的思路, 如果下一个结点不为空, 先递归下一个结点[递归递归], 然后在打印当前结点的数据, 因为非尾递归, 所以需要保存当前方法的栈帧, 造成栈帧资源的开销

参考代码

/*** file name : Test24LinkedListReverseOutput.java* created at : 4:36:30 PM Jun 4, 2015* created by 970655147*/package com.hx.test04;public class Test24LinkedListReverseOutput {// 给定一个头结点  输出从尾部到头结点的数据public static void main(String []args) {LinkedList ll = new LinkedList();for(int i=0; i<10; i++) {ll.add(i);}linkedListReverseOutput01(ll.head.next);Log.enter();Log.horizon();linkedListReverseOutput02(ll.head.next);}// 思路 : 利用栈的性质  先进后出public static void linkedListReverseOutput01(Node head) {Deque<Integer> tmp = new java.util.LinkedList<Integer>();Node node = head;while(node != null) {tmp.push(node.data);node = node.next;}while(tmp.size() > 0) {Log.logWithoutLn(tmp.pop() + " ");}}// 利用递归的性质  但是数据过大容易造成栈的溢出public static void linkedListReverseOutput02(Node head) {if(head.next != null) {linkedListReverseOutput02(head.next);}Log.logWithoutLn(head.data + " ");}}

效果截图

总结

两种方法均只需遍历一次, 前者使用了额外的堆空间, 后者使用了额外的方法栈空间

注 : 因为作者的水平有限，必然可能出现一些bug, 所以请大家指出！