25. K 个一组翻转链表

题目： https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

进阶：

你可以设计一个只使用常数额外空间的算法来解决此问题吗？
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

用栈来解决

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* reverseKGroup(struct ListNode* head, int k){
    struct ListNode *res = malloc(sizeof(struct ListNode));
    struct ListNode *p, *pre;

    res->next = head;
    pre = res;
    p = res->next;

    int cnt = 0;
    int i;

    struct ListNode *stack[5100];
    int stack_size = 0;

    while(p!= NULL)
    {
        stack_size ++;
        stack[stack_size-1] = p;
            
        p = p->next;
        cnt++;
        if(cnt % k == 0)
        {
            // begin pop
            while(stack_size)
            {
                pre->next = stack[--stack_size];
                pre = pre->next;
            }
        }
    }

    for(i=0; i<stack_size; ++i)
    {
        pre->next = stack[i];
        pre = pre->next;
    }
    pre->next = NULL;
    return res->next;
}