/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head == nullptr || head->next == nullptr)
return head;
ListNode* p1 = head; // p1始终指向已经翻转完成的子链表的尾部
ListNode* p2 = head->next; // p2始终指向未翻转的下一个结点
ListNode* start = head; // start始终指向已经翻转完成的子链表的头部
while(p2){
head = p2; // 当前存在未翻转结点时，head一定指向它，并在接下来对其进行翻转
p2 = p2->next; // p2探查下一个未翻转结点
head->next = start; // 完成新的子链表的头部连接
p1->next = p2; // 完成新的子链表的尾部连接
start = head; // 翻转完成，更新子链表起始位置
}
return head;
}
};
递归翻转链表中left到right间的结点
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* successor = nullptr; // 记录每轮递归中无需翻转的第一个结点
ListNode* reverseN(ListNode* head, int n){ // 翻转链表中前n个结点
if(n == 1){
successor = head->next;
return head;
}
ListNode* last = reverseN(head->next, n-1);
head->next->next = head;
head->next = successor;
return last;
}
ListNode* reverseBetween(ListNode* head, int left, int right) {
if(left == 1)
return reverseN(head, right);
ListNode* start = reverseBetween(head->next, left-1, right-1);
head->next = start;
return head;
}
};
