从尾到头打印链表

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);

大师兄

1. 题目描述

2. 解题思路

3. 代码