欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

剑指offer 06. 从尾到头打印链表

程序员文章站 2022-03-14 21:16:40
...

题目链接:https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/

目录

题目:

方法1:正向存入列表后,调用列表list类的.reverse()方法

方法2:[::-1]法

方法3:递归反向return法


题目:

剑指offer 06. 从尾到头打印链表

方法1:正向存入列表后,调用列表list类的.reverse()方法

注意学习题目中的class ListNode(object):写法,可以看作链表的节点类,具有val属性用来存值,具有next属性用来指向链表的下一个元素。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reversePrint(self, head):
        """
        :type head: ListNode
        :rtype: List[int]
        """
        tempList = []
        while head:
            tempList.append(head.val)
            head = head.next
        #print(tempList)
        tempList.reverse()
        #print(tempList)
        return tempList

方法2:[::-1]法

用于本题的[::-1]就是倒序的输出list,仅需要在return语句中进行一些改变,这种方法在效率上是最高的。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reversePrint(self, head):
        """
        :type head: ListNode
        :rtype: List[int]
        """
        tempList = []
        while head:
            tempList.append(head.val)
            head = head.next
        return tempList[::-1]

在这里也学习python中提供的各种列表角标操作方法,主要是数组的切分,Reference:https://blog.csdn.net/ITOMG/article/details/88683256,其中主要注意双引号的倒序思想和截断切分中的“负角标”思想。

>>> testList = [0,1,2,3,4,5,6,7,8,9]

>>> print(testList)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> print(testList[1:9])
[1, 2, 3, 4, 5, 6, 7, 8]
>>> print(testList[1:10])
[1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> print(testList[-1])
9
>>> print(testList[:-1])
[0, 1, 2, 3, 4, 5, 6, 7, 8]
>>> print(testList[::-1])
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
>>> print(testList[1:-1])
[1, 2, 3, 4, 5, 6, 7, 8]
>>> print(testList[1:-2])
[1, 2, 3, 4, 5, 6, 7]
>>> print(testList[2::-1])
[2, 1, 0]

方法3:递归反向return法

剑指offer 06. 从尾到头打印链表

如上图学习了参考答案中给出的递归return法,这里也记录一个自己理解递归的过程:一连串的多米诺骨牌,其中间距正好是骨牌的长度,把其中的左边用胶条和地粘在一起(防止骨牌倒下后的位移),之后从右边推导多米诺骨牌,会发现骨牌虽然倒下了,但是无法完全碰触地面,直到最后一块骨牌倒下后,会从后往前的开始一块块的接触地面,是一个非常形象的递归过程。

这里的代码在写法上看起来比较奇怪,解释为递归返回条件,即最后一块多米诺骨牌倒下后返回一个空列表[],之后按照从后往前的顺序,把每一块多米诺骨牌的值val加进来,另注在python语言中两个列表通过+号进行操作,例如[1]+[2]会得到[1,2]的结果。另注递归方法在时间,空间上性能均较差。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reversePrint(self, head):
        """
        :type head: ListNode
        :rtype: List[int]
        """
        if head:
            return self.reversePrint(head.next) + [head.val]
        else:
            return []

 

相关标签: 剑指offer