一、反转链表
题目要求
我的题解
既然是使用vector容器来做这道题，那么就在判断链表不为空的情况下把链表的结点全部放进vector容器中，然后调用reverse(v.begin(),v.end());函数将容器的元素反转，最后将容器中的元素赋值给一个新创建的链表并返回该链表即可。
具体代码
class Solution { public: ListNode* ReverseList(ListNode* pHead) { if(!pHead) return nullptr; vector<ListNode*>v; while(pHead){ v.push_back(pHead); pHead=pHead->next; } reverse(v.begin(),v.end()); ListNode *head=*v.begin(); ListNode *ptr=head; for(int i=1;i<v.size();i++){ ptr->next=v[i]; ptr=ptr->next; } ptr->next=NULL; return head; } };
ListNode *head=*v.begin(); 这段代码的意思是新建的head结点指向反转后容器中的第一个元素，因为v.begin()是一个迭代器，只有加上"*"解引用之后才是结点。最后让ptr的指针指向NULL，这样做是防止测试代码的时候不能正常的停止遍历，防止死循环。
二、链表内指定区间反转
题目要求
我的题解
这题的意思就是在链表中指定一段区间进行反转，我还利用vector容器来操作。
首先排除区间为一的情况，如果区间为一，也就是m==n，直接返回链表即可；然后将链表全部存进vector中，然后把m和n的区间表示出来，通过一个while循环把指定区间的结点值反转；最后再把容器中的元素取出来放进新建的链表并返回即可。
具体代码
class Solution { public: /** * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类 */ ListNode* reverseBetween(ListNode* head, int m, int n) { // write code here if(m==n) return head; vector<ListNode*> v; int l=m-1,r=n-1; while(head){ v.push_back(head); head=head->next; } while(l<r){ int k=v[l]->val; v[l]->val=v[r]->val; v[r]->val=k; l++; r--; } ListNode *L=*v.begin(); ListNode *ptr=L; for(int i=1;i<v.size();i++){ ptr->next=v[i]; ptr=ptr->next; } ptr->next=NULL; return L; } };
这样的思路很好理解吧，和第一题的步骤几乎一样，只是多了一个while循环来把指定区间的元素值进行反转，这样循序渐进可以加深这个借助vector容器来辅助解决问题的思想。
三、链表中的节点每k个一组翻转
题目要求
我的题解
这一题我想到的是要先分块进行翻转操作，最后再进行链表拼接。再三考虑下我选择了递归的方法，目的就是把所有的"块"翻转完之后能立刻拼接并返回该链表，这样不就能解决问题了吗。具体实现过程我会在该题具体代码的下面详解。
具体代码
class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { if(!head || k <= 1) return head; //空指针及不需要翻转的情况直接返回head ListNode* pre = nullptr; //pre指向右移前的当前结点 ListNode* cur = head; //记录当前ListNode ListNode* next = nullptr; //记录下一个ListNode //检测是否进行反转 for(int i = 0; i < k; i++) { //检测ListNode数量是否大于k if(!cur) return head; //若不大于直接返回头 cur = cur->next; //指向下一个ListNode } cur = head; //检测完毕后cur复原成头 for(int i = 0; i < k; i++) { next = cur->next; //记录后一个ListNode cur->next = pre; //cur指向前一个ListNode pre = cur; //pre成为新的头结点并右移 cur = next; //cur右移 } head->next = reverseKGroup(next, k); //此时k个ListNode翻转完毕，head其实就是反转后的pre return pre; //返回新的头 } };
这段代码的核心部分就从第二个for循环开始了，首先利用next指针记录组内第二个结点；然后将pre指针插入到当前结点之后，将pre结点左移，这样pre就代表头结点且值为当前结点的值，然后当前结点右移，指向之前next记录的位置；循环的最终结果是该组的结点完成翻转，且pre为与head指向相同，让head指向下一个结点的递归结点即可，最后全部翻转后返回pre，程序结束。
动态图解
