代码随想录算法训练营第三天 | 链表理论基础 | 206.反转链表

从老链表第一个元素开始，逐个取出

• 第一个取出的元素，让其next指向nullptr。由于改变其指向，会导致后续链表没有指向消失，所以要在这步之前将其后续元素的指向放在一个新变量中
• 再将后续结点的指向当前结点，不断反复运行就可以实现链表反转

难点就是如何在设置链表指向结点时，不同指针的关系不要混乱

#include <iostream>struct ListNode {int val;ListNode* next;ListNode(): val(0), next(nullptr) {}ListNode(int v): val(v), next(nullptr) {}ListNode(int v, ListNode* _next): val(v), next(_next) {}
};class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* cur = head, *pre = nullptr;for ( ; cur != nullptr; ) {ListNode* temp = cur->next;cur->next = pre;pre = cur;cur = temp;}return pre;}
};void show(ListNode* head) {for (auto* p = head; p != nullptr; p = p->next)std::cout << p->val << " ";std::cout << std::endl;
}int main()
{ListNode* l5 = new ListNode(5);ListNode* l4 = new ListNode(4, l5);ListNode* l3 = new ListNode(3, l4);ListNode* l2 = new ListNode(2, l3);ListNode* l1 = new ListNode(1, l2);show(l1);Solution s;ListNode* head = s.reverseList(l1);show(head);return 0;
}

核心代码在11行到23行

汇总