链表-高频-k个一组翻转链表

k个一组翻转链表

k个一组翻转链表.png

基本思路：
(1) 重点：寻找确定k 个一组范围，pre> [front, tail] > tailnext, 主要是tail,tail 必须非空
故while循环退出条件：cur->next != NULL
且主要不要使用 len--; 因为 cur->next && len-- ， 每次对len--, len--放到循环体内部，保证最多执行到0，也就是k 次；

        int len = k;
        while(cur->next && len) {
            cur=cur->next;
            len--;
        }

        if(len)
            break;

(2) 对k 个做翻转链表处理
(3)

struct ListNode* reverse(struct ListNode* head){
    struct ListNode* result= NULL;
    struct ListNode* cur=head;
    while(cur) {
        struct ListNode* next = cur->next;
        cur->next=result;
        result=cur;
        cur=next;
    }

    //print(result);
    return result;
}


struct ListNode* reverseKGroup(struct ListNode* head, int k){
    struct ListNode* dummy = (struct ListNode*) malloc(sizeof(struct ListNode));
    dummy->next=head;

    struct ListNode* pre=dummy;

    while(1) {

        struct ListNode* cur = pre;
        int len = k;
        while(cur->next && len) {
            cur=cur->next;
            len--;
        }

        if(len)
            break;

        struct ListNode* front = pre->next;
        struct ListNode* tail = cur;
        struct ListNode* tailnext= cur->next;

        //break tail and tailnext
        tail->next=NULL;
        //
        reverse(front);
        pre->next = tail;
        front->next=tailnext;
        //
        pre = front;

    }

    return dummy->next;
}