力扣206.反转链表 92.反转链表II

LeetCode 206. 反转链表（简单）

题目：反转一个单链表。

示例：

输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

解法一：迭代（双指针）

classSolution{public:ListNode*reverseList(ListNode*head){ListNode*prev=nullptr;ListNode*curr=head;while(curr){ListNode*next=curr->next;curr->next=prev;prev=curr;curr=next;}returnprev;}};

解法二：递归

classSolution{public:ListNode*reverseList(ListNode*head){if(!head||!head->next)returnhead;ListNode*newHead=reverseList(head->next);head->next->next=head;head->next=nullptr;returnnewHead;}};

LeetCode 92. 反转链表 II（中等）

题目：反转从位置left到right的链表节点（索引从 1 开始）。

示例：

输入: 1->2->3->4->5->NULL, left = 2, right = 4 输出: 1->4->3->2->5->NULL

解法：一次遍历 + 局部反转

思路：

1. 找到待反转部分的前一个节点pre和起始节点start。
2. 反转[left, right]区间内的节点，记录反转后的头尾。
3. 将pre连接到反转后的头，反转后的尾连接到后续节点。

classSolution{public:ListNode*reverseBetween(ListNode*head,intleft,intright){if(!head||left==right)returnhead;ListNodedummy(0);dummy.next=head;ListNode*pre=&dummy;// 1. 移动 pre 到 left 的前一个节点for(inti=1;i<left;++i){pre=pre->next;}// 2. 反转 [left, right] 区间ListNode*curr=pre->next;ListNode*prev=nullptr;for(inti=left;i<=right;++i){ListNode*next=curr->next;curr->next=prev;prev=curr;curr=next;}// 3. 连接pre->next->next=curr;// 原 left 节点的 next 指向 right 后面的节点pre->next=prev;// pre 指向反转后的头节点returndummy.next;}};

复杂度

• 时间：O(n)
• 空间：O(1)