从尾到头打印链表

1. 题目描述

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

2. 解题思路

可以从头到尾遍历一遍链表，将节点放入栈中，然后依次取出打印（后入先出）。

优化就是借助“递归”，先向下查找再打印输出，也可实现这种“后入先出”。可以类比二叉树的后序遍历。

3. 代码

用 JS 实现了简单实现了链表这种数据结构，这不是重点。

重点在printFromTailToHead函数。

class Node {
    /**
     * 节点构造函数
     * @param {*} value
     * @param {Node} next
     */
    constructor(value, next) {
        this.value = value
        this.next = next
    }
}

class List {
    constructor() {
        this.head = new Node(null, null)
    }

    /**
     * 从0开始计算，找到包括head在内的位于index的节点
     * @param {Number} index
     */
    find(index) {
        let current = this.head
        for (let i = 0; i < index; ++i) {
            current = current.next
        }
        return current
    }

    /**
     * 向index位置插入元素
     * @param {*} value
     * @param {Number} index
     */
    insert(value, index) {
        const prev = this.find(index)
        const next = new Node(value, prev.next)
        prev.next = next
    }
}

/**
 * 逆序打印链表
 * @param {Node} node
 */
function printFromTailToHead(node) {
    if (node.next) {
        printFromTailToHead(node.next)
    }
    node.value && console.log(node.value)
}

/**
 * 以下是测试代码
 */
let list = new List()
list.insert('a', 0)
list.insert('b', 1)
list.insert('c', 2)

printFromTailToHead(list.head)