题目：
面试tips：
询问面试官是否可以改变链表结构
思路：
1. 翻转链表，再遍历链表打印。
2. 想要实现先遍历后输出，即先进后出，因此可借助栈结构。
3. 可用隐式的栈结构，递归来实现。
代码实现：
1.
class ListNode:
def __init__(self, val = 0, next = None):
self.val = val
self.next = next
class myClass:
def printList(self, head):
# 前后指针翻转链表
prev, curr = None, head
while curr:
tmp = curr.next
curr.next = prev
prev, curr = curr, tmp
# 翻转后prev即指向新链表的头节点
# 打印链表
curr = prev
while curr:
print(curr.val)
curr = curr.next
if __name__ == '__main__':
# 构造测试用例 -- 用数组构造链表
arr = [5,4,2,3]
head = ListNode(arr[0]) if arr else None
curr = head
for i in range(1, len(arr)):
curr.next = ListNode(arr[i])
curr = curr.next
# 执行函数
a = myClass()
a.printList(head)
2.
class ListNode:
def __init__(self, val = 0, next = None):
self.val = val
self.next = next
class myClass:
def printList(self, head):
# 定义一个栈，用来存储遍历过的链表节点
stack = []
curr = head
while curr:
stack.append(curr)
curr = curr.next
# 打印链表值，这里pop出来也可释放内存
while stack:
node = stack.pop()
print(node.val)
if __name__ == '__main__':
# 构造测试用例 -- 用数组构造链表
arr = [5,4,2,3]
head = ListNode(arr[0]) if arr else None
curr = head
for i in range(1, len(arr)):
curr.next = ListNode(arr[i])
curr = curr.next
# 执行函数
a = myClass()
a.printList(head)3.
采用递归的思想 注意是递归到最后一个元素才开始打印 即要先写递归 后写打印代码
class ListNode:
def __init__(self, val = 0, next = None):
self.val = val
self.next = next
class myClass:
def printList(self, head):
# 递归打印链表 -- 递归就是栈 也就相当于使用了一个隐式的栈结构
# 终止条件
if not head:
return
# 单层递归逻辑 -- 先递归后打印
self.printList(head.next)
print(head.val)
if __name__ == '__main__':
# 构造测试用例 -- 用数组构造链表
arr = [5,2,6,3,5,4]
head = ListNode(arr[0]) if arr else None
curr = head
for i in range(1, len(arr)):
curr.next = ListNode(arr[i])
curr = curr.next
# 执行函数
a = myClass()
a.printList(head)
