题解 | #链表中的节点每k个一组翻转#

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
struct ListNode*partreverse(struct ListNode*head,int m,int n)
{
    struct ListNode *p = head, *pre, *temp, *s, *r;
    int i, j;
    s = head； //初始化s             
      for (i = 1; i < m; i++)
    {
        s = p;
        p = p->next;
    }
    r = pre = p;//找到要翻转的位置
    p = p->next;//将p指向下一位准备翻转
    for (j = m; j < n; j++)
    {
        temp = pre;//保留其前节点的位置
        pre = p;//将pre更新
        p = p->next;//更新p
        pre->next = temp;//将后一节点的next指向前一节点
    }//for循环使链表反转
    s->next = pre;//反转过后使前节点（s)指向翻转后的头结点
    r->next = p;//翻转后的尾结点指向后面的节点（p）
    if (m == 1)
        return pre;//特殊情况，当m == 1时，头结点发生变化，此时的头为pre
    return head;//一般情况，返回head
}
class Solution {
  public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        // write code here
        struct ListNode* p = head;//初始化p
        int n = 0;//用来给节点计数
        while (p != NULL)
        {
            p = p->next;
            n++;
        }
        if(n == 0 || k > n)
            return head;
                //判断特殊情况：当链表为空或者k>n时，直接返回原链表
        p = head;//重新初始化
        int times = n/k;//计算需要翻转的次数
        int j ,t = 1;//j,t为循环变量
        for(j = 0;j < times;j++)
        {
            p = partreverse(p,t,t+k-1);//翻转第t到t+k-1项，并且返回头指针
            t += k;//更新t，准备翻转下一组
        }
        return p;
                //最后，因为翻转的过程中head发生变化，而p始终为头指针，故返回p
    }
};