有一个含有n个元素的单链表,请将链表中的元素逆置并输出。
时间: 2023-04-21 16:02:31 浏览: 114
可以使用三个指针来实现链表的逆置操作。具体步骤如下:
1. 定义三个指针:p、q、r,分别指向当前节点、前一个节点和后一个节点。
2. 遍历链表,将当前节点的 next 指针指向前一个节点,然后将三个指针向后移动一个节点。
3. 当遍历到最后一个节点时,将链表的头节点指向最后一个节点。
4. 输出逆置后的链表。
下面是代码实现:
```python
def reverse_list(head):
if not head or not head.next:
return head
p = head
q = None
while p:
r = p.next
p.next = q
q = p
p = r
head = q
return head
# 测试代码
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def print_list(head):
while head:
print(head.val, end=' ')
head = head.next
print()
if __name__ == '__main__':
# 构造链表 1 -> 2 -> 3 -> 4 -> 5
head = ListNode(1)
p = head
for i in range(2, 6):
node = ListNode(i)
p.next = node
p = node
print_list(head)
# 输出:1 2 3 4 5
head = reverse_list(head)
print_list(head)
# 输出:5 4 3 2 1
```
运行结果:
```
1 2 3 4 5
5 4 3 2 1
```
阅读全文