25. 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,

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

解题思路：

1）如果链表为空或者k==1都无需翻转，返回即可。

2）如果k大于链表长度也无需翻转，返回即可。

3）用链表长度除以翻转区间长度，获取到有多少个需要翻转的区间(times)

4）逐个区间进行翻转，翻转后的区间链表存放在list中，单个区间翻转完成后合并翻转后的链表到final最终链表中。

5）把剩下部分的链表部分添加到final即完成k长度区间翻转。

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     struct ListNode *next; * }; */struct ListNode* reverseKGroup(struct ListNode* head, int k) {    if ( head == NULL || k == 1 )    {        return head;    }        int len = 0;    struct ListNode *list = head;    for ( ; list; list = list->next )    {        len += 1;    }        if ( k > len )    {        return head;    }        struct ListNode *next = NULL;    struct ListNode *final = NULL;    int times = len / k;    int cnt = 0;    while ( cnt < times )    {        list = NULL;        int index = 0;        for ( index = 0; index < k; index++ )        {            next = head->next;            head->next = list;            list = head;            head = next;        }                if ( final == NULL )        {            final = list;        }        else        {            next = final;            while ( next->next != NULL )            {                next = next->next;            }            next->next = list;        }        cnt += 1;    }        next = final;    while ( next->next != NULL )    {        next = next->next;    }    next->next = head;        return final;}