递归写法

反转整条单链表

可以借助这个写法深入理解递归的精髓 => （总结一下）进入下一层

下一层可以看作一条链表长度 - 1的新链表

ListNode* reverseList(ListNode* head) {
//    这里if => 既是递归的base，返回最后一个结点
//          => 又有对特殊情况的判断，当链表为空或只有一个结点，就没有反转的必要直接返回if(!head || !head->next) return head;ListNode* last = reverseList(head->next);
//    这行代码就是将该层所处在的结点的下一个结点指向自己head->next->next = head;
//    这行实际作用起在一开始链表的头节点 => 反转后变成尾巴啦 => 指向NULL
//    只是从其他地方的结点看这句话没什么用head->next = NULL;return last;
}

反转链表的任意区间

这里我们先简化问题，将区间左侧固定为头节点

需要注意的就是要记录后继结点 => 方便后续连接

因为这里头节点不是去做尾巴啦，而是中间一个结点，所以要获取后继结点

这里的n是从头节点向后数n个结点

ListNode* successor = NULL; // 后继结点
ListNode* reverseN(ListNode* head, int 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;
}

处理任意区间 => 不过是将问题转化成我们上述这个比较容易处理的方案

将指针向下遍历至要求的区间左侧的结点，这个时候再去reverseN 

=> 从逆角度去思考就好像需要被反转的区间左侧被固定了

class Solution {
public:ListNode* successor = NULL;ListNode* reverseN(ListNode* head, int 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);head->next = reverseBetween(head->next, left - 1, right - 1);return head;}
};

需要注意的是，不要写成下面这种

我知道你是怎么想的，但是你要注意，在递归的过程中，left和right已经改变啦，虽然这是常识，可是在思考问题的时候容易忽略，很正常啦，这个bug代码就是犯过的错误

ListNode* reverseBetween(ListNode* head, int left, int right) {if(left == 1) return reverseN(head, left - right + 1);head->next = reverseBetween(head->next, left - 1, right);return head;
}

迭代写法

反转整条和反转一部分没什么区别其实

=> 反转整条就看成从head->null

先给出反转整条的代码 =>[a, null)

ListNode* reverse(ListNode* a, ListNode* b) {ListNode *pre = NULL, *cur = a, *next = a;while(cur != NULL) {next = cur->next;cur->next = pre;pre = cur;cur = next;}return pre;
}

只要把while的条件稍加改变 => [a, b)

ListNode* reverse(ListNode* a, ListNode* b) {ListNode *pre = NULL, *cur = a, *next = a;while(cur != b) {next = cur->next;cur->next = pre;pre = cur;cur = next;}return pre;
}

再来加深一下递归的理解 => 25. K 个一组翻转链表 - 力扣（LeetCode）

ListNode* reverse(ListNode* a, ListNode* b) {ListNode *pre = NULL, *cur = a, *next = a;while(cur != cur) {next = cur->next;cur->next = pre;pre = cur;cur = next;}return pre;
}ListNode* reverseKGroup(ListNode* head, int k) {if(!head || !head->next) return head;ListNode* a = head, *b = head;for(int i = 0; i < k; i++) {
//        不足k个一组就不反转if(b == NULL) return head;b = b->next;}
//    根据递归层层返回，最终会得到刚开始反转后的新节点 => 也就是整个反转后的新节点ListNode* newHead = reverse(a, b);
//    因为我们的reverse是简化问题后的写法 => 相当于把左侧固定在头节点啦a->next = reverseKGroup(b, k);return newHead;
}