假设线性表(a1,a2,a3,…an)采用带头结点的单链表存储,请设计算法函数将带头结点的单链表head就地倒置,使表变成(an,an-1,…a3.a2,a1)。并构造测试用例进行测试
时间: 2023-06-12 15:03:02 浏览: 140
算法思路:
首先定义三个指针,分别指向当前节点(p)、前一个节点(pre)和后一个节点(post)。
然后遍历链表,每次将当前节点指向前一个节点,再将三个指针向后移动一位,直到遍历完整个链表。
最后将头结点指向倒置后的最后一个节点。
算法实现:
```python
def reverse_list(head):
if head is None or head.next is None:
return head
pre = None
p = head.next
post = p.next
while post is not None:
p.next = pre
pre = p
p = post
post = post.next
p.next = pre
head.next = p
return head
```
测试代码:
```python
# 定义节点类
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# 构造测试用例
head = ListNode()
p = head
for i in range(1, 6):
node = ListNode(i)
p.next = node
p = node
# 打印原链表
p = head.next
while p is not None:
print(p.val, end=" ")
p = p.next
print()
# 倒置链表
head = reverse_list(head)
# 打印倒置后的链表
p = head.next
while p is not None:
print(p.val, end=" ")
p = p.next
print()
```
测试结果:
```
1 2 3 4 5
5 4 3 2 1
```