跳至主要內容

从尾到头打印链表

微信公众号：储凡About 2 min

从尾到头打印链表

题目链接

题目描述

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

如输入{1,2,3}的链表如下图:

返回一个数组为[3,2,1]

0 <= 链表长度 <= 10000

刷题思路

单链表比较直接的想法就是：顺讯访问、按照链表结点循环即可，比较好的模型：

while (head != null) {
  // 结点向后
  head = head.next
}

代码实现

/*
 * @Description: 【简单】从尾到头打印链表
 * @Version: Beta1.0
 * @Author: 微信公众号：储凡
 * @Date: 2021-05-01 20:49:28
 * @LastEditors: 微信公众号：储凡
 * @LastEditTime: 2021-05-01 21:24:40
 */

/**
 * 单链表数据结构
 * @param x
 * @constructor
 */
function ListNode(x) {
  this.val = x
  this.next = null
}

/**
 * 从头出链表，按序放入数组，最后翻转数组
 * 偷懒写法
 * @param head
 * @returns {*[]}
 */
function printListFromTailToHeadOne(head) {
  const result = []
  while (head !== null) {
    result.push(head.val)
    // 下一个元素
    head = head.next
  }
  // 翻转并返回
  return result.reverse()
}

/**
 * 相比链表的头插，对数组array进行头插unshift()即可
 * @param head
 * @returns {*[]}
 */
function printListFromTailToHeadTwo(head) {
  const result = []
  while (head !== null) {
    // 头插
    result.unshift(head.val)
    // 下一个结点
    head = head.next
  }
  return result
}

/**
 * 先翻转链表【采用头插法】，再按序输出到数组中
 * @param head
 * @returns {*[]}
 */
function printListFromTailToHeadThree(head) {
  let reverseHead = new ListNode(-1)
  // 翻转链表
  while (head !== null) {
    const pre = head
    // 下一个结点
    head = head.next
    pre.next = reverseHead.next
    reverseHead.next = pre
  }
  // 重新整理 去掉val=-1的点
  reverseHead = reverseHead.next

  const result = []
  // 遍历链表
  while (reverseHead !== null) {
    result.push(reverseHead.val)
    // 下一个结点
    reverseHead = reverseHead.next
  }
  return result
}

一些建议