My solution with O(n) time and O(1) space


  • 0
    2

    The following is my explanation(use the example of the problem statement)

    1. 1->2->3->4->null k=2

    2. 0(auxiliary node)->1->2->3->4->null

    3. 0->3->4->null 1->2->null

    4. 0->3->4->null 2->1->null

    5. 0-2->1->3->4->null

    6. 0->2->1->null 3->4->null

    7. 0->2->1->null 4->3->null

    8. 0->2->1->4->3->null

    here is my code

    *typedef struct ListNode Node;
    void revers(Node head);
    struct ListNode
    reverseKGroup(struct ListNode
    head, int k) {
    if(k==0 || k==1 || head==NULL || head->next==NULL)
    return head;

    int tag=0;
    Node dummy,*p;
    p=&dummy;
    dummy.next=head;
    Node *q=p->next;
    
    while(p->next!=NULL)
    {
        Node *s=q;
        for(int i=0;i<k-1;++i)
        {
            s=s->next;
            if(s==NULL)
            {
                tag=1;
                break;
            }
        }
        if(tag==1)
            break;
        p->next=s->next;
        s->next=NULL;
        revers(q);
        q->next=p->next;
        p->next=s;
        for(int i=0;i<k;++i)
            p=p->next;
        q=p->next;
    }
    return dummy.next;
    

    }

    void revers(Node *head)
    {
    if(head==NULL || head->next==NULL)
    return;

    Node dummy,*p;
    dummy.next=NULL;
    p=head;
    Node *s=p;
    
    while(p!=NULL)
    {
        s=s->next;
        p->next=dummy.next;
        dummy.next=p;
        p=s;
    }
    

    }**


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.