从尾到头打印链表

题目描述

输入一个链表，从尾到头打印链表每个节点的值。

这个问题应该是很常见的，如何把一个单向链表进行从尾到头的输出。

方法一：按照我的习惯一般喜欢先考虑牺牲空间的做法。由于是最先读到的链表头需要最后输出，这是典型的栈结构特点，所以这里可以构建一个栈。将链表的内容依次存入栈，再从栈中取出即可。

public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        Stack<Integer> stack=new Stack<Integer>();
        while(listNode!=null){
            stack.push(listNode.val);
            listNode=listNode.next;     
        }
        ArrayList<Integer> list=new ArrayList<Integer>();
        while(!stack.isEmpty())
            list.add(stack.pop());
        return list;
    }
}

其实用数组，队列等也能实现。下面是数组版的，原理都大同小异。

public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        int count = 0;
        while(listNode.next != null) count++;
        int[] tmp = new int[count];
        for(int i = count - 1; i >= 0; i--) {
            tmp[i] = listNode.val;
            listNode = listNode.next;
        }
        for(int i = 0; i < count; i++) {
            res.add(tmp[i]);
        }
        return res;
    }
}

方法二：既然用栈可以解决问题，那么用递归应该也一样，毕竟递归的本质也是一个栈结构。

public class Solution {
    ArrayList<Integer> res = new ArrayList<Integer>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if(listNode != null) {
                //只是为了遍历，返回值不关心
            printListFromTailToHead(listNode.next);
            res.add(listNode.val);
        }
        return res;
    }
}

另一种递归思路，利用返回值,返回的是当前节点之后的所有节点。

public class Solution {
    public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if(listNode == null) return res;
        if(listNode.next != null) 
                res = printListFromTailToHead(listNode.next);
        res.add(listNode.val);
        return res;
    }
}

方法三：一般默认的是不修改输入数据，但是如果可以修改输入数据的话，我们只要将链表进行反转就可以实现要求。

public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        ListNode current = listNode;
        ListNode newhead = null;
        ListNode next = null;
        while(current != null) {
            next = current.next;     //进行断链并保存之后节点
            current.next = newhead; //断链重接，接到前半部分的头
            newhead = current;       //更新头
            current = next;          //更新需要断链的位置
        }
        while(newhead != null) {
            res.add(newhead.val);
            newhead = newhead.next;
        }
        return res;
    }
}

#

原理大致就是这个样子，画的不好凑合着看吧。