LeetCode 206. 反转链表简单题目反转一个单链表。示例输入: 1-2-3-4-5-NULL 输出: 5-4-3-2-1-NULL解法一迭代双指针classSolution{public:ListNode*reverseList(ListNode*head){ListNode*prevnullptr;ListNode*currhead;while(curr){ListNode*nextcurr-next;curr-nextprev;prevcurr;currnext;}returnprev;}};解法二递归classSolution{public:ListNode*reverseList(ListNode*head){if(!head||!head-next)returnhead;ListNode*newHeadreverseList(head-next);head-next-nexthead;head-nextnullptr;returnnewHead;}};LeetCode 92. 反转链表 II中等题目反转从位置left到right的链表节点索引从 1 开始。示例输入: 1-2-3-4-5-NULL, left 2, right 4 输出: 1-4-3-2-5-NULL解法一次遍历 局部反转思路找到待反转部分的前一个节点pre和起始节点start。反转[left, right]区间内的节点记录反转后的头尾。将pre连接到反转后的头反转后的尾连接到后续节点。classSolution{public:ListNode*reverseBetween(ListNode*head,intleft,intright){if(!head||leftright)returnhead;ListNodedummy(0);dummy.nexthead;ListNode*predummy;// 1. 移动 pre 到 left 的前一个节点for(inti1;ileft;i){prepre-next;}// 2. 反转 [left, right] 区间ListNode*currpre-next;ListNode*prevnullptr;for(intileft;iright;i){ListNode*nextcurr-next;curr-nextprev;prevcurr;currnext;}// 3. 连接pre-next-nextcurr;// 原 left 节点的 next 指向 right 后面的节点pre-nextprev;// pre 指向反转后的头节点returndummy.next;}};复杂度时间O(n)空间O(1)