剑指 Offer 24. 反转链表 - 力扣（LeetCode） (leetcode-cn.com)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre=nullptr;
ListNode* cur=head;
while(cur)
{
ListNode* nextnode=cur->next;
cur->next=pre;
pre=cur;
cur=nextnode;
}
return pre;
// if(head==NULL) return NULL;
// if(head->next == NULL) return head;
// ListNode* last = reverseList(head->next);
// head->next->next = head;
// head->next = NULL;
// return last;
}
};
注释掉的是递归写法
92. 反转链表 II - 力扣（LeetCode） (leetcode-cn.com)
递归写法，如果left==1，则进入reverseN函数，反转[1,right]的结点。
reverseN函数中，要记录下第right+1个结点，当区间内的反转完成后要让头指针指向那个right+1结点。
left-1，right-1这里就是记录到当前头节点的相对距离，head结点每次往后一个结点，相对距离就要减1，当left==1的时候就变成了reverseN的情况。
/**
* 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* node=nullptr;
ListNode* reverseBetween(ListNode* head, int left, int right) {
if(head==nullptr) return nullptr;
if(left==1)
{
return reverseN(head,right);
}
head->next=reverseBetween(head->next,left-1,right-1);
return head;
}
ListNode* reverseN(ListNode* head,int n)
{
if(n==1)
{
node=head->next;
return head;
}
ListNode* last=reverseN(head->next,n-1);
head->next->next=head;
head->next=node;
return last;
}
};
leetcode（剑指offer 24）-反转链表C++实现
原文：https://www.cnblogs.com/Jessicax/p/14961563.html