25. K 个一组翻转链表

思路：
写一个反转子链表的函数，输入（head,tail）,返回新的(head,tail).
每次先判断剩余长度是否足够k，找head和tail，并记录head的pre和tail的next，反转后指一指。

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode() : val(0), next(nullptr) {}
  7.  *     ListNode(int x) : val(x), next(nullptr) {}
  8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  9.  * };
  10.  */
  11. class Solution {
  12. public:
  13.     pair<ListNode*,ListNode*> myReverse(ListNode* head, ListNode* tail){
  14.         ListNode* pre = NULL;
  15.         ListNode* now = head;
  16.         while(pre!=tail){
  17.             ListNode* nex = now->next;
  18.             now->next = pre;
  19.             pre = now;
  20.             now = nex;
  21.         }
  22.         return make_pair(tail,head);
  23.     }
  25.     ListNode* reverseKGroup(ListNode* head, int k) {
  26.         ListNode* dummy = new ListNode(0);
  27.         dummy->next = head;
  28.         ListNode* pre = dummy;
  30.         while(head){
  31.             ListNode* tail = head;
  32.             for(int i=0;i<k-1;i++){
  33.                 tail = tail->next;
  34.                 if(tail==NULL){
  35.                     return dummy->next;
  36.                 }
  37.             }
  38.             ListNode* tailNext = tail->next;
  39.             pair<ListNode*,ListNode*> p= myReverse(head,tail);
  40.             ListNode* newHead = p.first;
  41.             ListNode* newTail = p.second;
  42.             pre->next = newHead;
  43.             newTail->next = tailNext; 
  44.             pre = newTail;
  45.             head = newTail->next;
  46.         }
  47.         return dummy->next;
  48.     }
  49. };