《剑指Offer》面试题五之从尾到头打印链表

2019-11-06 07:04:40

字体：大中小

来源：转载

供稿：网友

题目描述

输入一个链表的头结点，从尾到头反过来打印每个节点的值！

解题思路1

运用栈的数据结构先从头到尾依次进栈，再依次出栈。因为栈是先进后出的数据结构，所以实现了链表的翻转。

代码实现

package question;import java.util.*;/** * 作者：白芷 * 时间：2017/3/5 * 说明：从尾到头打印链表的值（栈结构） * */class ListNode{ PRotected int data; //存储的数据 protected ListNode next; //下一个节点 public void printListRever(ListNode head){ Stack<ListNode> stack=new Stack<ListNode>();//栈先进后出 ListNode node=head.next; while(node!=null){ //从头到尾进栈 stack.push(node); node=node.next; } while(!stack.isEmpty()){ //再从尾到头依次取出，实现翻转 node=stack.pop(); System.out.print(node.data+" "); } } public ListNode createNode(int data){ //创建链表结点 ListNode node=new ListNode(); node.data=data; return node; }}public class Question5 { public static void main(String[] args) { ListNode head=new ListNode(); ListNode list=head; for(int i=0;i<10;i++){//创建链表存储 10 9 8 7 6 5 4 3 2 1 (除头结点) list.next=list.createNode(i+1); list=list.next; } head.printListRever(head); } /** * 输出 * 10 9 8 7 6 5 4 3 2 1 * */}

解题思路2

既然用到了栈，那么自然就会想到递归。递归在本质上也是一个栈结构。

代码实现

public void printListRever(ListNode head){ ListNode node=head; if(node.next!=null){ node=node.next; printListRever(node); } System.out.print(node.data+" "); }

使用递归来实现这个问题看起来代码会简洁很多，但是，如果链表太过于长的话，会使函数调用的层级很深，从而可能会使函数的调用栈溢出。