剑指offer-从尾到头打印链表

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

题目：

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

输入：head = [1,3,2]
输出：[2,3,1]

注意看题目的伪代码，定义了节点。

 自己理解，以列表形式整体输入链表每个节点的值，然后让我们从尾到头输出节点的值。

python没有链表

所以，首先我们需要定义节点，

然后构造链表，即节点用指针串起来。

然后倒序输出，即先进后出（后进先出）典型的栈结构

解答题目之前，需要大家了解一点基础知识 

# Definition for singly-linked list.
class Node:#定义结点
     def __init__(self, x):
         self.val = x
         self.next = None
c=Node(1)
d=Node(2)
c.next=d
print(d.next,type(d.next),bool(d.next))
print(bool(d))#True虽然指针为空，但节点val有数，所以还是true
#https://blog.csdn.net/qq_37891604/article/details/122799338?spm=1001.2014.3001.5501
print(bool(None))#False

lst1=[1,2]
lst2=[3,4]
print(lst1+lst2)#列表是可以相加的

 第一种方法，用栈

# Definition for singly-linked list.
class Node:#定义结点
     def __init__(self, x):
         self.val = x
         self.next = None
class ListNode:#构造为链表
      def crtlis(self,lst):
          listnode=Node(lst[0])
          temp=listnode
          for i in lst[1:]:#切片的结果，一个新的列表对象
              node=Node(i)
              temp.next=node
              temp=temp.next
          return listnode
class Solution:#将链表从尾到头输出
    def reversePrint(self,ln):
        stack=[]
        while ln:#节点非空
            stack.append(ln.val)
            ln=ln.next
        return stack[::-1]#从尾到头输出列表
h=Solution()
a=ListNode()
b=a.crtlis([1,3,2])
print(h.reversePrint(b))
c=Node(1)
d=Node(2)
c.next=d
print(d.next,type(d.next),bool(d.next))
print(bool(c))#True虽然指针为空，但节点val有数，所以还是true
#https://blog.csdn.net/qq_37891604/article/details/122799338?spm=1001.2014.3001.5501
print(bool(None))#False

既然想到了用栈来实现这个函数，而递归的本质就是一个栈结构，于是很自然的就可以想到用递归实现。

# Definition for singly-linked list.
class Node:#定义结点
     def __init__(self, x):
         self.val = x
         self.next = None
class ListNode:#构造为链表
      def crtlis(self,lst):
          listnode=Node(lst[0])
          temp=listnode
          for i in lst[1:]:#切片的结果，一个新的列表对象
              node=Node(i)
              temp.next=node
              temp=temp.next
          return listnode
class Solution:
    # 返回从尾部到头部的列表值序列，例如[1,2,3]
    def reversePrint(self, listNode):
        # write code here
        list = []
        if listNode:
            #self.reversePrint(listNode.next)
            list = self.reversePrint(listNode.next)
            list.append(listNode.val)
        return list
h=Solution()
a=ListNode()
b=a.crtlis([1,3,2])
print(h.reversePrint(b))
d=a.crtlis([5,6,7])
print(h.reversePrint(d))

错误递归 ，思路一样，错误

出现在全局变量gloabl

通过输出的样例就可以理解

博主这个地方卡了半天，如果有同样疑问的可以去查询变量域

# Definition for singly-linked list.
class Node:#定义结点
     def __init__(self, x):
         self.val = x
         self.next = None
class ListNode:#构造为链表
      def crtlis(self,lst):
          listnode=Node(lst[0])
          temp=listnode
          for i in lst[1:]:#切片的结果，一个新的列表对象
              node=Node(i)
              temp.next=node
              temp=temp.next
          return listnode
lst = []
class Solution:
    def reversePrint(self, listNode):
        global lst
        if listNode:
            self.reversePrint(listNode.next)
            lst.append(listNode.val)
        return lst
h=Solution()
a=ListNode()
b=a.crtlis([1,2,45])
print(h.reversePrint(b))
d=a.crtlis([1,2,3])
print(h.reversePrint(d))