专栏首页陌无崖知识分享剑指offer:go实现从尾到头打印链表

剑指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, " ")
  }
}

但是我们仍然需要注意的是,在面对当链表的数据较长,利用栈调用的层次很深

从而有可能导致函数调用栈溢出。

本文分享自微信公众号 - golang技术杂文(gh_ebbdb61f463e),作者:无崖子天下无敌

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-12-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 剑指Offer-从尾到头打印链表

    package LinkedList; import java.util.ArrayDeque; import java.util.ArrayList; im...

    武培轩
  • 【剑指offer】从尾到头打印链表

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 剑指offer--从尾到头打印链表

    AI那点小事
  • 剑指 Offer 06. 从尾到头打印链表

    Zoctopus
  • 【剑指Offer】6. 从尾到头打印链表

    要逆序打印链表 1->2->3(3,2,1),可以先逆序打印链表 2->3(3,2),最后再打印第一个节点 1。而链表 2->3 可以看成一个新的链表,要逆序打...

    瑞新
  • 剑指offer - 从尾到头打印链表 - JavaScript

    发现后半段出栈的逻辑,其实就是将数组reverse反转。因此,借助 javascript 的 api,更优雅的写法如下:

    心谭博客
  • 《剑指offer》之从尾到头打印链表

    仅仅看这个题目,有点不知道怎么下手的感觉,意思明白,但是怎么做呢?首先我们的准备一个链表,题目给了提示,我们创建一个ListNode 类,内容如下

    程序员爱酸奶
  • 《剑指offer》05: 从尾到头打印链表

    遍历链表,每个链表结点值 push 进栈,最后将栈中元素依次 pop 到 list 中。

    程序员小浩
  • 【剑指offer】3.从尾到头打印链表

    要遍历链表就是不断找到当前节点的next节点,当next节点是null时,说明是最后一个节点,停止遍历。

    ConardLi
  • 剑指offer(5)——从尾到头打印链表

    说故事的五公子
  • 剑指offer No.3 从尾到头打印链表

    week
  • 剑指offer第4题:从头到尾打印链表

    题目要求我们从尾到头打印数组,首先应该想到我们肯定是需要对整个链表进行一个反序操作。所以联想到我们之前做过的反转链表题目,这道就解出来了。

    鹏-程-万-里
  • LeetCode 剑指 Offer 06. 从尾到头打印链表(swift)

    freesan44
  • 剑指Offer面试题:4.从尾到头打印链表

      到解决这个问题肯定要遍历链表。遍历的顺序是从头到尾的顺序,可输出的顺序却是从尾到头。也就是说第一个遍历到的结点最后一个输出,而最后一个遍历到的结点第一个输出...

    Edison Zhou
  • 剑指Offer 面试题06. 从尾到头打印链表

    可以利用栈的特性:先进后出。来完成这个题目,遍历head,遍历到为空为止,然后每一次遍历都取出val,压如栈中。

    TrueDei
  • 每日一题 剑指offer(从头到尾打印链表)

    编程是很多偏计算机、人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用。因此小白决定开辟一个新的板块“每日一题”,通过每天一道编程题目来强化...

    小白学视觉
  • [剑指offer] 从尾到头打印链表

    一种方法是利用栈来实现; 另外一种方法是利用三个指针把链表反转,关键是 r 指针保存断开的节点。

    尾尾部落
  • 从尾到头打印链表

    题目:输入一个链表的头结点,从尾到头反过来打印出每个结点的值。 链表结点定义如下: struct ListNode { int m_nKey; ...

    猿人谷
  • 从尾到头打印链表

    用户3003813

扫码关注云+社区

领取腾讯云代金券