反转链表的题型总结一下无外乎就这几种：
1.从头到尾反转链表
2.反转链表的前n个节点
3.反转链表的m到n个节点
4.反转链表从a节点到b节点左闭右开区间节点
5.k个一组反转链表
1.从头到尾反转链表
从头到尾反转链表是最基本的反转链表题目，无论是迭代法还是递归法都是非常基础和简单的，但是也是考察的重点，我参考了其他大佬的模板，将这两种整合一下，如下：
（1）迭代法：
class Solution { public: ListNode* reverseList(ListNode* head) { if(head == nullptr || head->next == nullptr) return head; ListNode* pPre = nullptr; ListNode* pCur = head; ListNode* pNext = nullptr; while(pCur != nullptr) { pNext = pCur->next; pCur->next = pPre; pPre = pCur; pCur = pNext; }
return pPre; } };
（2）递归法
class Solution { public: ListNode* reverseList(ListNode* head) { if(head == nullptr || head->next == nullptr) return head; ListNode* last = reverseList(head->next); head->next->next = head; head->next = nullptr; return last; } };
2.反转链表的前n个节点
虽然没有直接的这种题型，但其实反转从m到n个节点是跟这个有关系的
反转前n个节点其实和反转全部节点是一样的，在判断的时候，全部反转的条件是pCur != nullptr，而反转前n个的话可以找到第n+1个节点end，判断条件改成pCur != end，然后把原来的头结点head接到第n+1个节点end上就行了。
（1）迭代法：
// 反转链表的前n个节点,返回新的头结点 ListNode* reverseN(ListNode*head, int n) { ListNode* successor = head; for (int i = 0; i < n; i++) { if (successor == nullptr) { return head; } successor = successor->next; } ListNode* pPre = nullptr; ListNode* pCur = head; ListNode* pNext = nullptr; while(pCur != successor) { pNext = pCur->next; pCur->next = pPre; pPre = pCur; pCur = pNext; } head->next = successor; return pPre; }
（2）递归法：
ListNode* successor = nullptr; // 后驱节点 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; }
3.反转链表的m到n个节点
（1）迭代法：
迭代法的思路就是找到第m个节点，记录第m-1个节点，一趟遍历完成反转
class Solution { public: ListNode* reverseBetween(ListNode* head, int m, int n) { ListNode* pCur = head; ListNode* pPre = nullptr; ListNode* pNext = nullptr; ListNode* pPreBegin = nullptr; // m-1个节点 ListNode* pBegin = nullptr; // 第m个节点 for(int i=0;i<m-1;i++) { pPreBegin = pCur; pCur = pCur->next; } pBegin = pCur; for(int j=m;j<=n;j++) { pNext = pCur->next; pCur->next = pPre; pPre = pCur; pCur = pNext; } if(m != 1) { pPreBegin->next = pPre; } pBegin->next = pNext; return m==1? pPre : head; } };
（2）递归法：
这个题型跟反转前n个节点紧密相关，以为当m=1时，就是反转前n个节点，所以如下，其中的reverseN函数就是第二种题型里的函数，迭代和递归两个都可以：
ListNode* reverseBetween(ListNode* head, int m, int n) { if (m == 1) { return reverseN(head, n); } head->next = reverseBetween(head->next, m-1, n-1); return head; }
4.反转链表从a节点（假设a为头节点）到b节点左闭右开区间节点
反转所有节点的思路是，反转从a节点到nullptr节点的所有节点；而这个题型跟反转所有节点其实是一样的，变成了反转从a到b的节点，左闭右开，只需要改一下条件就行
ListNode* reverseList(ListNode* a, ListNode b) {
ListNode* pPre = nullptr;
ListNode* pCur = head;
ListNode* pNext = nullptr;
while(pCur != b)
{
pNext = pCur->next;
pCur->next = pPre;
pPre = pCur;
pCur = pNext;
}
return pPre;
}
5.k个一组反转链表
先反转前k个，再递归反转后面的，当然要注意如果不满足k个就不反转了，这个题跟第4种情况紧密相关
class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { //先反转以head开头的k个元素 //将第k+1个元素作为head递归调用reverseKGroup函数 //将上述两个过程的结果连接起来 //base case 如果最后的元素不足k个，就保持不变 if (head == nullptr) return nullptr; ListNode* a = head; ListNode* b = head; for (int i = 0; i < k; i++) { if (b == nullptr) return head; b = b->next; } ListNode* newHead = reverseListNode(a, b); // 先反转前k个元素 a->next = reverseKGroup(b, k); // 再递归反转后面的 return newHead; } private: ListNode* reverseListNode(ListNode* a, ListNode* b) { //实现一个函数，翻转从a到b的部分 ListNode* pCur = a; ListNode* pNext = nullptr; ListNode* pPre = nullptr; while (pCur != b) { pNext = pCur->next; pCur->next = pPre; pPre = pCur; pCur = pNext; } return pPre; // 返回新的头 } };