倒插模式通常指的是将链表中的节点顺序颠倒,即第一个节点变成最后一个节点,第二个节点变成倒数第二个节点,以此类推。下面是一个用C++实现的倒插模式程序,用于反转单链表:
```cpp
include
// 定义链表节点结构体
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
// 反转链表的函数
void invert(ListNode*& head) {
if (head == NULL || head->next == NULL) {
return; // 链表为空或只有一个节点,无需反转
}
ListNode *p = head->next; // 指向当前工作节点
ListNode *pn = NULL; // 指向工作节点的前驱节点
head->next = NULL; // 将头节点从链表中移除
while (p != NULL) {
pn = p->next; // 保存当前节点的下一个节点
p->next = head->next; // 将当前节点的下一个节点指向头节点
head->next = p; // 将头节点指向当前节点
p = pn; // 移动到下一个节点
}
}
// 辅助函数:打印链表
void printList(ListNode* head) {
ListNode* temp = head;
while (temp != NULL) {
std::cout << temp->val << " ";
temp = temp->next;
}
std::cout << std::endl;
}
// 辅助函数:创建链表
ListNode* createList(int arr[], int n) {
if (n == 0) return NULL;
ListNode* head = new ListNode(arr);
ListNode* current = head;
for (int i = 1; i < n; ++i) {
current->next = new ListNode(arr[i]);
current = current->next;
}
return head;
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr);
ListNode* head = createList(arr, n);
std::cout << "Original list: ";
printList(head);
invert(head);
std::cout << "Reversed list: ";
printList(head);
return 0;
}
```
在这个程序中,我们定义了一个`ListNode`结构体来表示链表的节点,然后实现了一个`invert`函数来反转链表。`invert`函数接受一个链表头节点的引用,并修改它以反转链表。我们还提供了辅助函数`printList`来打印链表和`createList`来根据数组创建链表。
请注意,这个程序假设链表中的节点是单向链表,并且每个节点只有一个指向下一个节点的指针。如果你的链表是双向链表或者有其他结构,你需要相应地调整代码。