python用栈反转一个链表
时间: 2023-11-30 22:30:57 浏览: 33
可以使用栈来反转一个链表的顺序。以下是用Python实现的示例代码:
```python
class Node:
def __init__(self, data):
self.data = data
self.next = None
def reverse_linked_list(head):
if not head:
return None
stack = []
current = head
while current:
stack.append(current)
current = current.next
# 弹出栈中的节点,改变指针方向
new_head = stack.pop()
current = new_head
while stack:
node = stack.pop()
current.next = node
current = node
current.next = None
return new_head
```
这里定义了一个简单的链表节点类 `Node`,其中 `data` 属性存储节点的数据,`next` 属性指向下一个节点。函数 `reverse_linked_list` 接受链表头节点作为参数,并使用一个栈来反转链表的顺序。先将链表中的所有节点按顺序入栈,再依次出栈并改变节点间的指针方向,最后返回新的头节点。
你可以使用以下代码来测试:
```python
# 创建链表:1 -> 2 -> 3 -> 4 -> 5
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)
# 反转链表
new_head = reverse_linked_list(head)
# 遍历打印反转后的链表
current = new_head
while current:
print(current.data, end=' ')
current = current.next
```
输出结果为:`5 4 3 2 1`,表示链表成功反转。