剑指Offer(06)从头到尾打印链表

今天是小呆刷题的第 21 天，今天的题目是：剑指 Offer 的第 6 题，从头到尾打印链表

题目要求

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例：

1 2	`输入：head = [1,3,2] 输出：[2,3,1]`

提示：

0 <= 链表长度 <= 10000

解题思路

首先这道题的输入是从头到位，但是输出却是从尾到头。也就是FILO先进后出，这妥妥的就是栈结构嘛。所以我们可以遍历一遍链表，然后将每一项都存入数组中，最后反转数组即可。

栈结构

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {number[]}
 */
var reversePrint = function (head) {
  let arr = [],
    node = head,
    ans = []
  while (node !== null) {
    arr.push(node.val)
    node = node.next
  }

  /* 不用API反转数组
    for(let i = arr.length - 1; i >= 0; i--) {
      ans.push(arr[i])
    }
  	return ans
  */
  return arr.reverse() // 利用API反转数组
}

当然，利用API的话，我们还有更加简洁的写法，毕竟 JavaScript 无所不能~（偷笑）

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {number[]}
 */
var reversePrint = function (head) {
  let ans = [],
    node = head
  while (node !== null) {
    ans.unshift(node.val)
    node = node.next
  }
  return ans
}

既然用到了栈结构，那小呆很自然也能想到使用递归，毕竟递归本质上就是一种栈结构。

递归算法

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {number[]}
 */
var reversePrint = function (head) {
  if (head === null) return []
  const ans = reversePrint(head.next)
  ans.push(head.val)
  return ans
}