题解 | #链表中的节点每k个一组翻转# 纯C源码 注释详细

 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @param k int整型 
 * @return ListNode类
 */
struct ListNode* reverseKGroup(struct ListNode* head, int k ) {
    // write code here
    if(head==NULL||head->next==NULL)
        return head;
    struct ListNode* H=malloc(sizeof(struct ListNode));
    H->next=head;//由于可能对链表头结点进行修改，提前创建一个头结点连接链表
    struct ListNode* cur=head;
    struct ListNode* Newhead=H;//用于指向每组反转区间的头结点
    int flag=0;
    int i;
    while(cur!=NULL&&cur->next!=NULL)
    {
        struct ListNode *p,*q,*temp=cur;
        q=cur;//保存每组反转链表的第一个节点，即反转后与原链表相连的节点
        //判断是否越界，越界直接返回
        for(i=0;i<k;i++)
        {
            if(temp==NULL)
            {
                flag=1;
                break;
            }
            temp=temp->next;
        }
        if(flag==1)
            break;
        //头插法反转链表
        for(i=0;i<k&&cur->next!=NULL;i++)
        {   
            p=cur;
            cur=cur->next;
            p->next=Newhead->next;
            Newhead->next=p;
        }
        //正好反转无溢出节点时特殊处理
        if(i<k)
        {
            q->next=NULL;
            cur->next=Newhead->next;
            Newhead->next=cur;
            break;
        }
        q->next=cur;//反转后的链表与原链表相连
        Newhead=q;//头结点迭代
    }
    return H->next;
}