C++链表反转最优算法：逐行代码讲解

在C++中，链表的反转是一项常见的操作，也是面试中的热门考点。本文将带你深入解析一个经典且高效的链表反转算法，并附带详细的逐行代码解释，帮助你彻底掌握它。

以下是实现链表反转的C++代码：cppstruct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {}};

ListNode* reverseList(ListNode* head) { ListNode* prev = nullptr; ListNode* curr = head; while (curr != nullptr) { ListNode* nextTemp = curr->next; // 临时保存当前节点的下一个节点 curr->next = prev; // 将当前节点的next指针指向前一个节点 prev = curr; // 更新prev为当前节点 curr = nextTemp; // 更新curr为下一个节点 } return prev; // 返回反转后的头节点}

逐行代码解释：

struct ListNode { ... };: 定义了一个名为 'ListNode' 的结构体，表示链表的节点。每个节点包含两部分： - int val: 存储节点的值。 - ListNode* next: 指向链表中下一个节点的指针。2. ListNode(int x) : val(x), next(nullptr) {}: 这是 'ListNode' 的构造函数，用于创建新的链表节点，并初始化节点的值为 'x'，并将 'next' 指针初始化为 'nullptr'，表示新节点初始时不指向任何节点。3. ListNode* reverseList(ListNode* head) { ... }: 定义了一个名为 'reverseList' 的函数，用于反转链表。它接受一个指向链表头节点的指针 'head' 作为参数，并返回反转后的链表的新头节点。4. ListNode* prev = nullptr;: 定义一个名为 'prev' 的指针，初始值为 'nullptr'。它用于在遍历过程中记录当前节点的前一个节点。5. ListNode* curr = head;: 定义一个名为 'curr' 的指针，初始值为 'head'。它用于在遍历过程中指向当前正在处理的节点。6. while (curr != nullptr) { ... }: 这是一个循环结构，用于遍历整个链表，直到 'curr' 指针为空，即到达链表尾部。7. ListNode* nextTemp = curr->next;: 在反转当前节点的指向之前，先将当前节点的下一个节点的地址临时保存在 'nextTemp' 指针中。这是至关重要的，因为如果直接修改 'curr->next'，将会丢失对下一个节点的引用。8. curr->next = prev;: 进行链表反转的核心操作。将当前节点 'curr' 的 'next' 指针指向 'prev'，即将当前节点的指向反转，使其指向前一个节点。9. prev = curr;: 将 'prev' 指针更新为 'curr'，即移动到下一个节点。10. curr = nextTemp;: 将 'curr' 指针更新为之前保存的 'nextTemp'，即移动到下一个节点。11. return prev;: 循环结束后，'prev' 指针将指向反转后的链表的最后一个节点，也就是新链表的头节点。函数返回 'prev'，即返回反转后的链表。

总结

这段代码通过迭代的方式，巧妙地改变链表节点的指向，实现了高效的链表反转。其时间复杂度为O(n)，其中n为链表长度，因为它只遍历了链表一次。理解并掌握这个算法对于学习数据结构和算法以及应对技术面试都非常有帮助。