设有一个线性表E=｛e1,..en｝、设计一算法将其逆置，使元素次 序颠倒，要求逆线性表占用原线性表空间，并用单链表存储表示。

算法步骤如下：

1. 定义三个指针：p1指向当前节点，p2指向当前节点的前一个节点，p3指向当前节点的后一个节点。

2. 初始化p1为头节点，p2为空，p3为p1的下一个节点。

3. 依次遍历链表，将p1的next指向p2，然后移动p2、p1、p3指针，使它们分别指向当前节点、下一个节点和下下个节点。

4. 直到p1指向尾节点，此时p2指向倒数第二个节点，将p1的next指向p2，链表逆置完成。

5. 返回头节点即可。

具体实现如下：

def reverse_linked_list(head):
    if head is None or head.next is None:
        return head

    p1 = head
    p2 = None
    p3 = p1.next

    while p3 is not None:
        p1.next = p2
        p2 = p1
        p1 = p3
        p3 = p3.next

    p1.next = p2
    head.next = None
    head = p1

    return head

时间复杂度为O(n)，空间复杂度为O(1)。

相关问题

．设有一个线性表E={e1, e2, … , en-1, en}，设计一个算法，将线性表逆置，即使元素排列次序颠倒过来，成为逆线性表E’={ en , en-1 , … , e2 , e1 }，要求逆线性表占用原线性表空间，并且用顺序表和单链表两种方法表示，分别用两个程序来完成。

为了逆置一个线性表，无论它是顺序表还是单链表，我们都需要遍历整个列表并将元素逐个移动到新的位置。这里提供两种实现策略：

**顺序表（数组）逆置算法：**
1. 初始化两个指针，一个指向第一个元素（i=0），另一个指向最后一个元素（j=n-1）。
2. 循环进行，直到两个指针相遇：
a. 交换当前元素：`E[i] = E[j]`
b. 指针向中间移动：`i++`, `j--`
3. 完成后，整个顺序表就被逆置了。

**单链表逆置算法：**
1. 定义三个指针：`prev` (初始为空)，`current` 和 `next` 都指向头结点。
2. 循环遍历链表，更新每个节点的`next` 指针：
a. 将`current` 的下一个节点赋给`temp` (`temp = current.next`)
b. 将`current` 的`next` 设为`prev` (`current.next = prev`)
c. 更新指针：`prev = current`, `current = temp`
3. 当`current` 为空时，说明已到达链表尾部。设置新链表的头结点为`prev`（原来的尾结点）。

以下是简单的伪代码形式：

**顺序表逆置（Array）：**

function reverseSequentialList(E, n):
   i = 0
   j = n - 1
   while i < j:
       swap(E[i], E[j])
       i++
       j--

**单链表逆置（Linked List）：**

function reverseLinkedList(head):
   prev = None
   current = head
   while current is not None:
      next_node = current.next
      current.next = prev
      prev = current
      current = next_node
   head = prev

设有一线性表e=(e1 , e2 , … , en-1 , en)，其逆线性表定义为e'=( en , en-1 , … , e2 , e1)，请设计一个算法，将线性表逆置，要求逆线性表仍占用原线性表

的存储空间。

算法思路：

1. 定义两个指针，分别指向线性表的第一个元素和最后一个元素。

2. 交换两个指针所指向的元素，并将指针向中间移动一位，直到两个指针相遇。

3. 完成逆置。

算法实现：

void reverseList(int *e, int n) {
int i, temp;
for (i = ; i < n / 2; i++) {
temp = e[i];
e[i] = e[n - i - 1];
e[n - i - 1] = temp;
}
}

调用该函数即可将线性表逆置，逆线性表仍占用原线性表的存储空间。