剑指offer：go实现从尾到头打印链表
作者 | 陌无崖
转载请联系授权
题目描述
输入一个链表的头节点，从尾到头打印出每个节点的值
链表
解这道题之前，首先来回顾一下数据结构中有关链表的基本知识
定义
链表是一种物理存储单元上非连续，非顺序的存储结构
特点
1、节点在运行的时候才会被动态创建
2、节点包含两个部分：数据域和指针域
3、链表中没有闲置的内存，因此空间效率比数组高
4、构建链表时，不需要特别知道原始数据的长度
链表的基本实现
定义节点
type object interface{}
//定义节点
type Node struct {
value object
next *Node
}定义链表对象
// 定义一个链表
type ListNode struct {
size int
head *Node
tail *Node
}初始化链表
func (l *ListNode) Init() {
(*l).size = 0
(*l).head = nil
(*l).tail = nil
}添加元素
// 添加元素
func (l *ListNode) Append(node *Node) {
if node == nil {
return
}
(*node).next = nil
if (*l).size == 0 {
(*l).head = node
} else {
oldTail := (*l).tail
(*oldTail).next = node
}
(*l).tail = node
(*l).size++
}知道这些，我们就可以构建一个链表了
解题思路
对于上一题，很多人在看到的时候，基本都会想到，将链表的首尾进行交换反转，但是如果，我们的面试官，不让我们的原始链表结构发生变化呢？因此我们通常需要更好的办法，我们可以想一下如果对于1，2，3，4，5.这样的数据，需要我们输出5，4，3，2，1，我们会想到什么数据结构呢?很明显这是一个先进后出的模式，因此我们可以利用栈，但是我们总不能在构建一个栈吧，那么我们如何编写一个函数，让它完成栈的操作呢？那就是非我们的递归函数了。递归在运行的时候就是存储在栈中，因此我们便可利用这一点。知道了这，我们的代码会出乎意料的简单，如下：
func (l *ListNode) TailPrint_two(head *Node) {
if head != nil {
l.TailPrint_two(head.next)
fmt.Print(head.value, " ")
}
}但是我们仍然需要注意的是，在面对当链表的数据较长，利用栈调用的层次很深
从而有可能导致函数调用栈溢出。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-12-23，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
相关产品与服务
对象存储
对象存储（Cloud Object Storage，COS）是由腾讯云推出的无目录层次结构、无数据格式限制，可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限，无需分区管理，适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。