leetcode25. Reverse Nodes in k

Reverse Nodes in k"/>

leetcode25. Reverse Nodes in k

题目：题目链接

这题是hard诶，题目本身难度其实还好，但我debug是真的hard…
思路：把这题拆开，首先解决如何反转k个结点的链表？
首先创建一个头结点root，root->next=nullptr。然后依次插入结点。
然后我们再输出root->next，这样是不是就反转了链表呀。知道了逻辑，我们开始敲代码：

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* root = new ListNode();ListNode* dummy_node = root;while(head){ListNode* root_next_node = root->next;root->next = head;ListNode* head_next_node = head->next;head->next = root_next_node;head = head_next_node;}return dummy_node->next;}
};

参考例题：反转列表

好，解决了反转k个结点的列表的问题，我们只需要判断剩下的结点到底是否>k，否则不需要反转剩下的了。

那么，我们就要从反转中得到一些信息。什么信息？反转后列表的第一个结点。以及该列表的下一个结点，因为这个结点是我们下次反转(如果需要反转的话)的起点。

还有一点，我们对于整个列表而言还需要一个头结点，因为我们要反转很多次⌊n/k⌋。所以我们要每次都把反转好的链表加入到头结点后面，注意头结点每次都要是当前答案链表的最后一个元素哦。！！
其他的细节看代码就可以了：

/*** 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* reverse(ListNode* head, int k, ListNode*& next_node) {//反转从head开始的k个结点，并第k+1个结点赋值给next_node。注意最后一个是引用，因为要修改实际值哦ListNode* root = new ListNode();//头结点while (k--) {//执行k次，每次把head结点插入到root后面，这样就可以反转了ListNode* p = root->next;root->next = head;ListNode* q = head->next;head->next = p;head = q;next_node = q;}return root->next;}ListNode* reverseKGroup(ListNode* head, int k) {if (!(head && head->next)) return head;//如果没有或只有一个，直接返回就可以了ListNode* root = new ListNode();//用来当头结点，方便操作ListNode* begin = head;//每次将要反转链表的第一个结点ListNode* res = root;//用来保存root的头结点，因为最后是要输出第一个结点while (head){begin = head;for (int i = 1; i < k; ++i) {head = head->next;if (!head) {//如果没有k个，直接把后面的结点都接到root后面，然后返回就可以了root->next = begin;return res->next;}}//正常表示有k个root->next = reverse(begin, k, head);//执行反转操作，返回被反转链表的第一个结点root = begin;//将root指向答案链表的最后一个元素}return res->next;}};

大概就是这样了，其他的细节只要你动手实现，应该就可以看懂的。加油加油加油！！！