Python通过尾递归法实现链表的反转操作

"""
皮蛋编程(https://www.pidancode.com)
创建日期：2022/4/7
功能描述：Python通过尾递归法实现链表的反转操作
"""


class Node:

    # 构造函数初始化节点对象
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:

    # 初始化head
    def __init__(self):
        self.head = None

    def reverseUtil(self, curr, prev):

        # 如果是最后一个节点，则将其设置为head
        if curr.next is None:
            self.head = curr

            # 将下一个节点设置为上一个节点
            curr.next = prev
            return

        # 保存 curr.next 节点
        next = curr.next

        # 更新next
        curr.next = prev

        self.reverseUtil(next, curr)

    # 对链表进行反转
    def reverse(self):
        if self.head is None:
            return
        self.reverseUtil(self.head, None)

    # 在开始位置插入节点函数
    def push(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node

    # 打印输出链表
    def printList(self):
        temp = self.head
        while (temp):
            print(temp.data, end=" ")
            temp = temp.next


# 测试程序
llist = LinkedList()
llist.push(8)
llist.push(7)
llist.push(6)
llist.push(5)
llist.push(4)
llist.push(3)
llist.push(2)
llist.push(1)

print("给定的链表")
llist.printList()

llist.reverse()

print("\n反转后的链表")
llist.printList()