专栏首页全部文章Day 3:从尾到头打印链表

Day 3:从尾到头打印链表

剑指Offer_编程题——从尾到头打印链表

题目描述:

输入一个链表,按链表从尾到头的顺序返回一个ArrayList。

具体要求:

时间限制: C/C++ 1秒,其他语言2秒 空间限制: C/C++32M,其他语言64M

具体思路:

思路1: 1、先构造一个链表 2、定义一个栈,将链表元素放入到栈中 3、利用栈的先进后出,实现从尾到头返回 4、取出栈中元素放入到ArrayList,然后遍历   我们用java来实现这个思路:

import java.util.ArrayList;
public class Solution{
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<Integer>();
		ArrayList<Integer> result = new ArrayList<Integer>();
		ListNode temp = listNode;//这里需要构造一个ListNode类
		while ( temp != null ) {//需要先判断链表时候为空
			list.add( temp.val );//定义节点
			temp = temp.next;
		}
		for ( int i = list.size()-1; i>=0; i-- ) {
			result.add( list.get(i) );//遍历获得一个 ArrayList链表输出。
		}
		return result;
    }
}

  其效果如图所示:

思路2:让尾结点与头结点进行交换,然后让之前的数据插入到头指针之前 我们用python来实现这个思路

class Solution:
	def printListFromTailToHead(self, listNode):
		ret = []
		pTmp = listNode
		while pTmp:
			ret.insert(0, pTmp.val)
			pTmp = pTmp.next
		return ret

  其效果如图所示:

思路3:开辟一个新的list空间,将输入的链表list进行遍历,逆序并返回。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
# Python 2.7
 
class Solution:
    # 返回从尾部到头部的列表值序列,例如[1,2,3]
    def printListFromTailToHead(self, listNode):
        l = list()
        while listNode:
            l.append(listNode.val)
            listNode = listNode.next
        num = len(l)
        ArrayList = []
        while (num > 0):
            ArrayList.append(l[num-1])
            num -= 1
        return ArrayList
        # write code here

  在思路3的基础上我们继续缩小代码量。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
# Python 2.7
 
class Solution:
    # 返回从尾部到头部的列表值序列,例如[1,2,3]
    def printListFromTailToHead(self, listNode):
        l = list()
        while listNode:
            l.append(listNode.val)
            listNode = listNode.next
        return l[::-1]  #更简单的代码
        # write code here

总结

  本道题主要考察链表的相关知识,包括链表的逆序,还有栈和链表的相结合,达到链表的从尾到头输出。不过这里需要注意的是,在这道题中,listNode表示的是一个链表的节点,节点含有值和下一个节点指针,不能取len,更不能进行迭代。因此,我们在代码中用的是while()语句,而不是for()。同时,还是和之前两道题一样,任何一道编程题的代码、方法都不是唯一的,没有标准的答案,只是参考。思路不一样决定代码就不一样。因此我们要不断拓宽我们的思路,只有思路正确,才能写出正确的代码。继续加油,争取早日找到工作,Good Luck!!!

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构(五)——链表

      上篇文章我们给大家介绍了队列,主要包括稀疏数组的含义以及相关二者之间的转换思路和及其实现,之后又介绍了队列的基本思想和用数组来模拟队列将其进行实现,通过模拟...

    stefan666
  • Day63:数据流中的中位数

    背景知识介绍:   在做题之前,首先给大家介绍堆排序。在维基百科中是这样介绍堆排序的。堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆...

    stefan666
  • 面试汇总(九):数据结构与算法常见面试总结(二)——堆与栈、数组、排序

      上一篇文章我们介绍了在面试中数据结构中树的常见的面试题。这篇文章我们继续给大家介绍常见的问题。

    stefan666
  • php7 list()、session及其他模块的修改实例分析

    本文实例讲述了php7 list()、session及其他模块的修改。分享给大家供大家参考,具体如下:

    砸漏
  • Redis命令详解:Lists

    List是Redis的基础数据类型之一,类似于Java中的LinkedList。一个列表最多包含232个元素,常被用作模拟队列操作,接下来我们具体介绍一下Lis...

    Jackeyzhe
  • ShellExecute 启动外部程序 参数详细介绍

    ShellExecute的功能是运行一个外部程序(或者是打开一个已注册的文件、打开一个目录、打印一个文件等等),并对外部程序有一定的控制。 目录 1基本简介 2...

    hbbliyong
  • 为什么我会认为SAP是世界上最好用最牛逼的ERP系统,没有之一?

    为什么我认为SAP是世界上最好用最牛逼的ERP系统,没有之一?玩过QAD、Tiptop、用友等产品,深深觉得SAP是贵的有道理!       一套好的ERP系...

    SAP梦心
  • [Python爬虫]新闻网页爬虫+jieba分词+关键词搜索排序

    版权声明:本文为博主原创文章,转载请注明原文作者和原文地址链接,谢谢。 https://bl...

    后端技术漫谈
  • 在Entity Framework中使用存储过程(三):逻辑删除的实现与自增长列值返回

    本篇文章通过实例的方式,讨论两个在EF使用存储过程的主题:如何通过实体和存储过程的映射实现逻辑删除;对于具有自增长类型主键的数据表,在进行添加操作的时候如何将正...

    蒋金楠
  • 新公众号将没有留言功能 / 微信支付两年打败了支付宝

    微信团队为进一步规范公众平台生态环境,后续新注册的账号将没有留言功能,「最近三个月内注册,但尚未使用留言功能的账号将被收回留言权限。」

    知晓君

扫码关注云+社区

领取腾讯云代金券