线性表元素逆置reverse函数
时间: 2024-09-20 17:06:17 浏览: 25
线性表的元素逆置通常是指将线性表中的元素顺序反转。在计算机科学中,这可以通过各种数据结构如数组、链表等来实现。对于数组,可以创建一个新的数组存储原数组的倒序元素;对于链表,可以采用迭代或递归的方式遍历链表,并更新节点的指针,使其指向前一个节点而不是下一个节点。
以下是几种常见的逆置操作:
1. 数组逆置:通过两指针,一个从头开始,一个从尾开始,交换它们指向的元素,然后两个指针分别向中间移动,直到相遇。
2. 链表逆置:对单链表而言,可以设置三个指针,第一个指向当前节点,第二个指向下一个节点,第三个保存第二个节点的指针,然后依次调整这三个指针,使得当前节点的next指向前一个节点,直到遍历完整个链表。
```python
def reverse_array(arr):
start = 0
end = len(arr) - 1
while start < end:
arr[start], arr[end] = arr[end], arr[start]
start += 1
end -= 1
# 对于链表:
def reverse_linked_list(head):
prev = None
curr = head
while curr:
next_temp = curr.next
curr.next = prev
prev = curr
curr = next_temp
return prev
```
相关问题
试分别以顺序表和单链表作存储结构,各编写一个实现线性表就地逆置的算法
顺序表的就地逆置(即不需要额外空间)可以使用两个指针交换的方式来实现,从头和尾开始双向推进。以下是C++的实现:
```cpp
void reverse_seq_list(SeqList& list) {
int start = 0; // 指向第一个元素
int end = list.size() - 1; // 指向最后一个元素
while (start < end) {
std::swap(list[start], list[end]);
start++;
end--;
}
}
```
这里假设`SeqList`是一个自定义的顺序表类型,包含一个`size()`函数获取当前元素个数以及`swap`方法用于交换元素。
对于单链表,由于单链表无法直接访问其前驱节点,我们需要临时创建一个新的链表来实现逆置。以下是C++的链表版本:
```cpp
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
void reverse_link_list(ListNode*& head) {
ListNode* prev = nullptr;
ListNode* curr = head;
ListNode* nextTemp;
while (curr != nullptr) {
nextTemp = curr->next;
curr->next = prev;
prev = curr;
curr = nextTemp;
}
head = prev;
}
```
这个函数接受链表头指针,并通过不断更新`prev`, `curr`和`nextTemp`指向,实现了链表的逆置。
要求编写函数实现带头结点的单链线性表的就地逆置操作函数。L是一个带头结点的单链表,函数ListReverse_L(LinkList &L)要求在不新开辟节点的前提下将单链表中的元素进行逆置,如原单链表元素依次为1,2,3,4,则逆置后为4,3,2,1。
以下是实现带头结点的单链线性表的就地逆置操作函数ListReverse_L的代码:
```
void ListReverse_L(LinkList &L) {
if (L == NULL || L->next == NULL) {
// 空表或只有一个结点,无需逆置
return;
}
// pre: 前驱结点;p: 当前结点;q: 后继结点
ListNode *pre = NULL, *p = L->next, *q = p->next;
while (p != NULL) {
p->next = pre; // 反转当前结点的指针域
pre = p; // 更新前驱结点
p = q; // 更新当前结点
if (q != NULL) {
q = q->next; // 更新后继结点
}
}
L->next = pre; // 更新头结点的指针域
}
```
该函数采用前插法的思路进行链表逆置,遍历链表时每次将当前结点的指针域反转,同时更新前驱、当前和后继结点,直到遍历到最后一个结点。最后需要更新头结点的指针域,使其指向新的第一个结点。