线性表就地逆置算法：顺序表与单链表实现

线性表是一种常见的数据结构，而将其就地逆置是一项基础操作。本文将分别使用顺序表和单链表两种存储结构实现线性表的原地逆置算法，并提供 Python 代码示例。

1. 顺序表实现

顺序表使用连续的存储空间存储数据元素，因此可以通过交换对称位置的元素实现就地逆置。

def reverse_seq_list(seq_list):
    left = 0
    right = len(seq_list) - 1

    while left < right:
        seq_list[left], seq_list[right] = seq_list[right], seq_list[left]
        left += 1
        right -= 1

    return seq_list

# 示例使用
my_list = [1, 2, 3, 4, 5]
reversed_list = reverse_seq_list(my_list)
print(reversed_list)

代码解释：

定义 reverse_seq_list 函数，接收一个顺序表作为参数。
使用 left 和 right 两个指针分别指向顺序表的首尾元素。
在 left 小于 right 的情况下，循环执行以下操作：
- 交换 left 和 right 位置的元素。
- left 指针右移一位，right 指针左移一位。
返回逆置后的顺序表。

2. 单链表实现

单链表通过指针连接各个数据元素，因此可以通过改变指针指向实现就地逆置。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_linked_list(head):
    prev = None
    curr = head

    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node

    return prev

# 示例使用
# 创建链表：1 -> 2 -> 3 -> 4 -> 5
head = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node5 = ListNode(5)

head.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

# 逆置链表
reversed_head = reverse_linked_list(head)

# 输出逆置后的链表
while reversed_head:
    print(reversed_head.val)
    reversed_head = reversed_head.next

代码解释：

定义 ListNode 类，表示单链表的节点。
定义 reverse_linked_list 函数，接收链表头节点作为参数。
使用 prev、curr 和 next_node 三个指针遍历链表，并改变指针指向：
- prev 指针指向已经逆置的链表部分的最后一个节点。
- curr 指针指向当前正在处理的节点。
- next_node 指针指向下一个待处理的节点。
循环执行以下操作，直到 curr 指针为空：
- 保存 curr 节点的下一个节点 next_node。
- 将 curr 节点的 next 指针指向 prev 节点，实现反转。
- 将 prev 指针移动到 curr 节点。
- 将 curr 指针移动到 next_node 节点。
返回逆置后的链表的头节点 prev。

总结

本文介绍了使用顺序表和单链表两种存储结构实现线性表就地逆置的算法，并提供了 Python 代码示例。顺序表的实现方法较为简单，但需要额外的空间存储临时变量；而单链表的实现方法无需额外空间，但代码相对复杂。选择哪种方法取决于实际应用场景的需求。