剑指offer JZ6 从尾到头打印链表
1. 题目描述
2. 思路分析：
一个简单的算法题，考察链表的基本使用。函数printListFromTailToHead返回的是一个ArrayList类型，那我就先new一个ArrayList类型的对象作为返回值。单向链表只能从头到尾访问，而要求从尾到头输出。逆序输出，第一个考虑到利用栈。马上想到struct stackNode…喂，我们在用Java呢！ Java里的java.util.*里面自带Stack，所以很自然，我们先顺序把每个结点的值依次push到Stack里，然后再pop进待返回的ArrayList对象中。
代码1：利用Stack实现逆序输出
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
/*创建储存反转结果的ArrayList Obj*/
ArrayList<Integer> list = new ArrayList<>();
/*实现反转操作的Stack*/
Stack<Integer> stack = new Stack<>();
/*建立一个临时的引用*/
ListNode p = listNode;
/*遍历链表，元素入栈*/
while(p!=null){
stack.push(p.val);
p=p.next;
}
/*将链表元素反序放到结点中*/
while(!stack.isEmpty()){
list.add(stack.pop());
}
return list;
}
}
做是做对了，就是有点慢。再想想，单链表是不是一棵退化的二叉树，而二叉树是不是有个后序遍历，而二叉树是不是又是个简单的图，图是不是有个DFS深度优先搜索？那妥了嘛，我们可以用递归的方式来逆序输出这个链表，代码多简单…自测试可以通过，然后提交直接StackOverflowError…JVM栈爆了！这说明这个JVM环境里系统栈不够使啊。。。
代码2： 递归实现逆序输出（StackOverflowError）
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
/*创建储存反转结果的ArrayList Obj*/
ArrayList<Integer> list = new ArrayList<>();
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
/*递归一直到当前结点为空*/
if(listNode!=null){
printListFromTailToHead(listNode.next);
list.add(listNode.val);
}
return list;
}
}
那考虑一下直接对链表进行翻转？因为返回的是个ArrayList对象，那么可以先依次把元素放入ArrayList，用Collections.reverse()方法来进行数组反转。(这个Collections.reverse一看就是个属于类的static方法)
代码3： 利用Collections.reverse()方法
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.ArrayList;
import java.util.*;
public class Solution {
/*创建储存反转结果的ArrayList Obj*/
ArrayList<Integer> list = new ArrayList<>();
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
/*依次放入元素一直到当前结点为空*/
while(listNode!=null){
list.add(listNode.val);
listNode=listNode.next;
}
/*直接反转链表*/
Collections.reverse(list);
return list;
}
}
既然可以用方法直接反转，那我们也可以用经典的三个指针的方法来反转链表，然后再顺序输入。
代码4： 经典3指针反转链表
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
// import java.util.ArrayList;
import java.util.*;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
/*创建储存反转结果的ArrayList Obj*/
ArrayList<Integer> list=new ArrayList<>();
/*经典的三指针反转链表*/
ListNode reverse=null;//存放翻转后链表
ListNode cur=listNode;//当前结点
ListNode temp=null;//用于暂存当前结点
/*当前结点不为空*/
while(cur != null){
temp=cur.next; //保存后一个结点
cur.next=reverse; //把当前结点的next指向反转后表头
reverse=cur;//把当前结点链到翻转后链表上
cur=temp;//把当前结点指针往后以为
}
while(reverse != null){
list.add(reverse.val);
reverse=reverse.next;
}
return list;
}
}