Cut, reverse, merge: Solution in C


  • 0
    S

    Has anyone coded a better solution in C? This one takes 16 ms.

     /*
     Algo: Break list into 2. reverse the second half. Join alternatively.
     */
    struct ListNode* reverse(struct ListNode *head){
        //reverse linked list
        struct ListNode *prev = NULL;
        struct ListNoe *next = NULL;
        while(head){
            next = head->next;
            head->next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
    
    
    void reorderList(struct ListNode* head) {
        if(!head || !head->next)
            return;
        int lt = 1, end, i;
        struct ListNode *h1=head,*h2=head, *t1=NULL, *t2=NULL;
        while((h1 = h1->next)!=NULL){
            lt++;
        }
        h1=head;
        end = (lt/2+lt%2);
        for(i=0;i<end-1;i++){
            h1 = h1->next;
        }
        h2 = h1->next;
        h1->next = NULL;
        h1 = head;
        h2 = reverse(h2);
        while(h1 && h2){
            t1 = h1->next;
            t2 = h2->next;
            h1->next = h2;
            h2->next = t1;
            h1=t1;
            h2=t2;
        }
    }

Log in to reply
 

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