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

链表中的节点每k个一组翻转

https://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @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 || k==1) return head;
    struct ListNode* H=(struct ListNode*)malloc(sizeof(struct ListNode));
    H->next=head;
    struct ListNode *pre=H;;//前一个节点
    struct ListNode* pstart;//保留反转前第一个节点
    struct ListNode* pend;//反转后第一个结点
    struct ListNode* cur=head,* nex;
    int i=0;
    while(cur!=NULL)
    {
        if(i==0)
        {
            pstart=cur;
        }
        nex=cur->next;
        cur->next=pre->next;
        pre->next=cur;
        cur=nex;
        i++;
        if(i==k)
        {
            pre=pstart;
            i=0;
        }
    }
    pstart->next=NULL;
    if(i!=0)//再反转
    {
         struct ListNode* pstart1=pre->next;//保留反转前第一个节点
         cur=pre->next;
         while(cur!=NULL)
         {
            nex=cur->next;
            cur->next=pre->next;
            pre->next=cur;
            cur=nex;
         }
        pstart1->next=NULL;
    }
       

    return H->next;
}
思路:先将链表k个一组全部反转,最后不满k个再反转一遍
难点:反转前第一个结点在插入反转后要接上下个反转后的第一个结点,最后一个要接上null

#链表中的节点每k个一组翻转#
全部评论

相关推荐

头像
不愿透露姓名的神秘牛友
02-28 22:51
点赞 评论 收藏
转发
点赞 收藏 评论
分享
牛客网
牛客企业服务