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

tags: linked-list

之前Leetcode上做过reverse nodes，这个是它的升级版。

想法是，每次数出k个node作为一组，将tail->next置为NULL，放入inverse函数里进行反转，再把反转后的list一组一组合并起来。

需要注意的是，最后一组不要反转，按照原样连接到结果list中。

代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *reverseKGroup(ListNode *head, int k) {
        int count = 1;
        ListNode * superHead = new ListNode(0);
        superHead->next = head;//super head
        ListNode * prevGroupTail = superHead;
        ListNode * nextGroupHead = head;
        ListNode * thisGroupHead = NULL;
        ListNode * p = NULL;
        while(nextGroupHead != NULL){
            thisGroupHead = nextGroupHead;
            p = thisGroupHead;
            while(count < k && p != NULL){
                p = p->next;
                count++;
            }
            count = 1;
            if(p == NULL){//last group, don't reverse
                nextGroupHead = NULL;
                prevGroupTail->next = thisGroupHead;
                continue;
            }
            else{//not the last group
                nextGroupHead = p->next;
                p->next = NULL;
            }
            p = reverse(thisGroupHead);
            prevGroupTail->next = p;
            while(prevGroupTail->next != NULL){
                prevGroupTail = prevGroupTail->next;//move to prev group tail
            }
        }
        p = superHead->next;
        delete superHead;
        return p;
    }
    ListNode * reverse(ListNode *head){
        ListNode * p1, * p2, * p3;
        if(head->next == NULL){
            return head;
        }
        else{
            p1 = NULL;
            p2 = head;
            while(p2 != NULL){
                p3 = p2->next;
                p2->next = p1;
                p1 = p2;
                p2 = p3;
            }
            return p1;
        }
    }
};