您的位置: 首页  >  文章  >  从头到尾打印链表

从头到尾打印链表

分类: 文章 • 2025-03-18 08:45:09

文章目录

从头到尾打印链表

题目位置（点击链接）
代码位置（点击链接）

方法1：

思路：
硬做，放入列表，翻转列表

class Solution:
    def printListFromTailToHead(self, listNode):
        newList = []
        while listNode:
            newList.append(listNode.val)
            listNode = listNode.next
        return newList[::-1]

运行时间：29ms 占用内存：5848k

方法2：

思路：
使用栈的先进后出特性，全部压入，然后全部弹出

class Solution:
    def printListFromTailToHead(self, listNode):
        stack = []
        while listNode:
            stack.append(listNode.val)
            listNode = listNode.next        
        list = []
        while stack:
            list.append(stack.pop())
        return list

运行时间：25ms 占用内存：5732k

涉及知识点：

什么是链表？

链表的特性
当进行插入和删除操作时，链表操作的时间复杂度仅为O(1)。另外，因为链表在内存中不是连续存储的，所以可以充分利用内存中的碎片空间。

链表的种类
链表包括单链表，双向链表，循环单链表，循环双链表。

单链表，由各个元素之间通过一个指针彼此链接。元素之间不能相互指向。每个元素包含两部分：数据成员和一个称为next的指针。
从头到尾打印链表
双向链表，每个链表元素既有指向下一个元素的指针，又有指向前一个元素的指针，其中每个结点都有两种指针。每个元素包含两部分：数据成员，一个称为pre的指针，一个称为next的指针。
从头到尾打印链表

循环链表，是在单链表和双向链表的基础上，使最后一个结点指向第一个结点从而实现循环。
从头到尾打印链表

什么是栈？

堆栈就是只能在一端插入和删除数据的链表，这个端就叫做栈顶（top），最后一个添加的数据第一个被删除。因此，这也叫后进先出（LAST IN FIRST OUT）链表或是先进后出链表（FIRST IN LAST OUT）。

举个例子，餐厅的盘子堆，盘子洗完要堆到上面，而不是插到下面的某个位置（相信不会有人那么做）。当厨师要用到盘子时从最上面的开始拿。即最先放在堆里的盘子会被最后一个用到。
从头到尾打印链表
堆栈有两种操作：

  • 进栈指令（PUSH）：在栈中现有元素顶部添加一个元素，新加入的元素变为最顶端的元素。
  • 出栈指令（POP）：取出栈顶元素，删除栈中的这个元素。

有些情况下，栈的最大长度有限。如果栈中元素已经达到最大长度，再用进栈指令会造成堆栈上溢出（stack overflow），相似的，如果堆栈已空还用出栈指令会造成堆栈下溢出（stack underflow）。

将列表当做堆栈使用

操作 描述
s = [] 创建一个栈
s.append(x) 往栈内添加一个元素
s.pop() 在栈内删除一个元素
not s 判断是否为空栈
len(s) 获取栈内元素的数量
s[-1] 获取栈顶的元素

python列表方法使得列表可以很方便的作为一个堆栈来使用，用 append() 方法可以把一个元素添加到堆栈顶。用不指定索引的 pop() 方法可以把一个元素从堆栈顶释放出来。例如：

>>> stack = [3, 4, 5]
>>> stack.append(6)
>>> stack.append(7)
>>> stack
[3, 4, 5, 6, 7]
>>> stack.pop()
7
>>> stack
[3, 4, 5, 6]
>>> stack.pop()
6
>>> stack.pop()
5
>>> stack
[3, 4]

列表切片

Python中符合序列的有序序列都支持切片（slice），例如列表，字符串，元组。
格式：【start: end :step】

索引
索引包括：正索引和负索引两部分，如下图所示，以a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]为例：
从头到尾打印链表
start:起始索引，从0开始，-1表示结束
end：结束索引
step：步长，end-start，步长为正时，从左向右取值。步长为负时，反向取值。
注意：切片的结果不包含结束索引，即不包含切的最后一位

a=[1,2,3,4,5,6]

#省略全部，代表截取全部内容，可以用来将一个列表拷给另一个列表
b1=a[:] 
print(b1)
结果：[1, 2, 3, 4, 5, 6]

#从位置0开始到结束，每次增加1，截取。不包含结束索引位置
b=a[0:-1:1] 
print(b)
结果：[1, 2, 3, 4, 5]

#省略起始位置的索引，以及步长。默认起始位置从头开始，默认步长为1，结束位置索引为3
c1=a[:3] 
print(c1)
结果：[1, 2, 3]

#从第一个位置到第留给位置，每3个取一个值
c=a[0:5:3] 
print(c)
结果：[1, 4]

#反向取值
d=a[5:0:-1]
print(d)
结果：[6, 5, 4, 3, 2]

#反转列表
d1=a[::-1]
print(d1)
结果：[6, 5, 4, 3, 2, 1]

相关推荐