首页单链表就地逆置c++源代码

单链表就地逆置c++源代码

时间: 2024-11-02 19:08:20 浏览: 90

单链表就地逆置（即原地反转），是指不用额外的数据结构，直接修改原链表节点指针，使其从头到尾形成一个新的逆序链表。这里是一个简单的C++实现示例： ```cpp #include <iostream> using namespace std; // 定义链表节点结构体 struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; // 就地反转链表函数 ListNode* reverseList(ListNode* head) { if (head == NULL || head->next == NULL) { return head; // 如果链表为空或只有一个元素，无需反转 } ListNode* prev = nullptr; // 创建前驱节点 ListNode* curr = head; // 当前节点 // 遍历链表，每次改变当前节点的指向，将prev更新为curr while (curr != NULL) { ListNode* temp = curr->next; // 保存下一个节点 curr->next = prev; // 更新当前节点指向prev prev = curr; // 移动prev到curr curr = temp; // 移动curr到下一个节点 } return prev; // 返回新的头节点 } int main() { // 测试代码，创建并反转链表 ListNode* list = new ListNode(1); list->next = new ListNode(2); list->next->next = new ListNode(3); cout << "Original List: "; printList(list); // 打印原始链表 list = reverseList(list); // 反转链表 cout << "Reversed List: "; printList(list); // 打印反转后的链表 delete list; return 0; } // 辅助函数：打印链表 void printList(ListNode* node) { while (node != NULL) { cout << node->val << " -> "; node = node->next; } cout << "NULL" << endl; }

阅读全文