一起创业网-为互联网创业者服务

倒插模式程序怎么写

倒插模式通常指的是将链表中的节点顺序颠倒,即第一个节点变成最后一个节点,第二个节点变成倒数第二个节点,以此类推。下面是一个用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`来根据数组创建链表。

请注意,这个程序假设链表中的节点是单向链表,并且每个节点只有一个指向下一个节点的指针。如果你的链表是双向链表或者有其他结构,你需要相应地调整代码。