以不同的储存结构实现线性表的就地逆转算法
时间: 2024-10-07 09:03:29 浏览: 23
线性表的就地逆转算法是指只使用原数组空间来翻转元素顺序,而不创建新的数据结构。这个过程可以应用到不同的存储结构,如数组或链表。
1. **数组实现**:
对于固定大小的数组,我们可以使用双指针法。初始化两个指针,一个指向数组开始(索引0),另一个指向数组结尾(索引长度-1)。然后交换这两个指针所指向的元素,并同时将它们向对方移动一位,直到两个指针相遇或交错。这样就能完成数组的就地逆转。
```python
def reverse_array_in_place(arr):
left = 0
right = len(arr) - 1
while left < right:
arr[left], arr[right] = arr[right], arr[left]
left += 1
right -= 1
```
2. **链表实现**:
对于动态大小的链表,可以遍历整个链表,每次将当前节点的next指向前一个节点,直到遍历完整个链表。这里不需要额外的空间,因为链表本身已经提供了反转的“空间”。
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_linked_list(head):
prev = None
current = head
while current:
temp = current.next
current.next = prev
prev = current
current = temp
return prev
```
阅读全文