leetcode 25 -- Reverse Nodes in k-Group

Reverse Nodes in k-Group

题目：
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example,
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5

---

题意：
给定k值和一个不定长度链表，要求按照每K个值反转字符串，返回反转后的结果。

---

思路：
设置一个新头节点，创建一个反转字符串的函数，满足条件长度等于K，那么就传参k+1个节点，因为反转后字符串我们还要保存其头节点，reverse反转函数返回的就是k+1长度串的新头节点，然后连接起来即可。

---

代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    //反转K+1个节点
    ListNode *reverse(ListNode *pre, ListNode *end){
        if(pre == NULL || pre->next == NULL){
            return pre;
        }
        //反转字符串需要保存3个节点
        ListNode *p = pre->next;
        ListNode *q = p->next;
        while(q != end){
            ListNode *next = q->next;  
            q->next = pre->next;  
            pre->next = q;  
            q = next;  
        }  
        p->next = end;  
        return p;  
    }

    ListNode* reverseKGroup(ListNode* head, int k) {
        if(head == NULL){
            return head;
        }
        ListNode *new_head = new ListNode(0);
        new_head->next = head;
        int cnt = 0;
        ListNode *pre = new_head;
        ListNode *cur = head;

        while(cur != NULL){
            cnt++;
            ListNode *next = cur->next;
            //判断是否满足长度值，满足即调用反转函数。
            if(cnt == k){
                pre = reverse(pre, next);
                cnt = 0;
            }
            cur = next;
        }
        return new_head->next;
    }
};