从尾到头打印链表

题目：输入一个链表的头节点，从尾到头反过来打印出每个节点的值。
链表数据结构：

function ListNode(val) {
    this.val = val;
    this.next = null;
}

解法一：反转链表后正序打印。

var printListReversingly = function(head) {
    var prevNode = null,
          currNode = head,
          tmpNode;
    while(currNode != null){   //反转链表
          tmpNode = currNode.next;
          currNode.next = prevNode;
          prevNode = currNode;
          currNode = tmpNode;   
    }
    pNode = prevNode;   //遍历反转链表
    while(pNode != null){
          console.log(pNode.val);
          pNode = pNode.next;
    }
}

解法二：遍历链表，将节点推入栈中。当遍历完节点后，从栈顶开始逐个输出节点的值。

var printListReversingly = function(head) {
    var pNode = head,
        pStack = new Array();  //基于数组实现栈
    while(pNode != null){
        pStack.push(pNode);  //遍历节点入栈
        pNode = pNode.next;
    }
    while(pStack.length != 0){
        console.log(pStack.pop().val);  //从栈顶出栈
    }
};

解法三：递归。先输出后一个节点的值，再输出当前节点自身的值。

var printListReversingly = function(head) {
    if(head != null){
        if(head.next != null){
            printListReversingly(head.next);
        }
        console.log(head.val);
    }
};

缺点：当链表非常长的时候，会导致函数调用层级很深，从而有可能导致函数调用栈溢出。