首页 > 其他 > 详细

从尾到头打印链表

时间:2016-03-02 20:07:43      阅读:112      评论:0      收藏:0      [点我收藏+]

题目:输入一个链表,从尾到头打印链表每个节点的值。 

思路:链表是不可以随机访问的,所以如果不借助辅助空间的话,每打印一个节点就会遍历一遍链表,时间复杂度为O(n^2)。那么就需要以空间换取时间,因为是倒着遍历链表,所以栈是最好的选择。只需要遍历一遍链表入栈。然后遍历栈,出栈。这样时间复杂度为O(n)。

实现代码:

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.*;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if(listNode == null)
            return new ArrayList<Integer>();
        Stack<Integer> stack = new Stack<Integer>();
        ArrayList<Integer> ret = new ArrayList<Integer>();
        ListNode head = listNode;
        while(head != null) {
            stack.push(head.val);
            head = head.next;
        }
        while(!stack.isEmpty()) {
            ret.add(stack.pop());
        }
        return ret;
    }
}

 

从尾到头打印链表

原文:http://www.cnblogs.com/wxisme/p/5236151.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!