剑指offer JZ6 从尾到头打印链表 Java解法

• • 1. 题目描述
  • 2. 思路分析：
  • • 代码1：利用Stack实现逆序输出
    • 代码2： 递归实现逆序输出（StackOverflowError）
    • 代码3： 利用Collections.reverse()方法
    • 代码4： 经典3指针反转链表

一个简单的算法题，考察链表的基本使用。函数printListFromTailToHead返回的是一个ArrayList类型，那我就先new一个ArrayList类型的对象作为返回值。单向链表只能从头到尾访问，而要求从尾到头输出。逆序输出，第一个考虑到利用栈。马上想到struct stackNode…喂，我们在用Java呢！ Java里的java.util.*里面自带Stack，所以很自然，我们先顺序把每个结点的值依次push到Stack里，然后再pop进待返回的ArrayList对象中。

import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public ArrayList printListFromTailToHead(ListNode listNode) {
        
        ArrayList list = new ArrayList<>();
        
        Stack 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环境里系统栈不够使啊。。。

import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    
    ArrayList list = new ArrayList<>();
    public ArrayList printListFromTailToHead(ListNode listNode) {
        
        if(listNode!=null){
            printListFromTailToHead(listNode.next);
            list.add(listNode.val);
        }
        return list;
    }
}

那考虑一下直接对链表进行翻转？因为返回的是个ArrayList对象，那么可以先依次把元素放入ArrayList，用Collections.reverse()方法来进行数组反转。(这个Collections.reverse一看就是个属于类的static方法)

import java.util.ArrayList;
import java.util.*;
public class Solution {
    
    ArrayList list = new ArrayList<>();
    public ArrayList printListFromTailToHead(ListNode listNode) {
        
        while(listNode!=null){
            list.add(listNode.val);
            listNode=listNode.next;
        }
        
        Collections.reverse(list);
        return list;
    }
}

既然可以用方法直接反转，那我们也可以用经典的三个指针的方法来反转链表，然后再顺序输入。

// import java.util.ArrayList;
import java.util.*;
public class Solution {    
    public ArrayList printListFromTailToHead(ListNode listNode) {
        
        ArrayList 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;
    }
}