3.设计算法，分别用顺序存储和链式存储实现线性表的倒置，要去用最少的附加存储空间来完成

线性表的倒置，即反转线性表的元素顺序，通常可以分为顺序存储和链式存储两种情况。

**顺序存储（数组）实现：**
对于顺序存储的线性表，由于元素是连续存放在内存中的，我们无法直接交换相邻元素的位置。一种常见的解决方案是双指针法，从两端向中间遍历并逐个交换元素。这个过程不需要额外的存储空间，时间复杂度为O(n)，其中n是列表长度。

def reverse_array(arr):
    left = 0
    right = len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1

**链式存储（链表）实现：**
链表的情况更简单，因为每个节点包含指向下一个节点的引用，可以直接修改节点的next指针来达到反转效果。同样不需要附加存储空间，只需要遍历整个链表即可。

class Node:
    def __init__(self, data=None, next=None):
        self.data = data
        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