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
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61