Python栈的应用：链表的反转

2023-04-11 00:00:00 python 链表 反转

链表的反转是一个经典的栈的应用问题。我们可以用栈来保存链表中的所有节点，然后依次弹出节点，将其指向前一个节点，实现链表的反转。

具体操作步骤如下：

  1. 依次将链表中的所有节点压入栈中；
  2. 依次弹出栈中的节点，并将其指向前一个节点；
  3. 将最后一个节点作为反转后的链表的头节点返回。

下面是用 Python 实现链表反转的代码演示：

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

def reverse_linked_list(head):
    stack = []
    while head:
        stack.append(head)
        head = head.next

    new_head = None
    if stack:
        new_head = stack.pop()
        current = new_head
        while stack:
            node = stack.pop()
            current.next = node
            current = node
        current.next = None

    return new_head

# 构造一个链表
head = Node('p')
head.next = Node('i')
head.next.next = Node('d')
head.next.next.next = Node('a')
head.next.next.next.next = Node('n')
head.next.next.next.next.next = Node('c')
head.next.next.next.next.next.next = Node('o')
head.next.next.next.next.next.next.next = Node('d')
head.next.next.next.next.next.next.next.next = Node('.com')

# 反转链表
new_head = reverse_linked_list(head)

# 输出反转后的链表
while new_head:
    print(new_head.value, end='')
    new_head = new_head.next

输出结果如下：

domcnaidip

相关文章