A C solution, 13ms, beats 100%(?) , O(n) time, O(1) space


  • 0
    F

    Divide the list from middle, to pLeft & pRight
    reverse pRight, and then intersects the two lists.

    struct ListNode* reverseList(struct ListNode *head)
    {
        if (head==NULL) return NULL;
        struct ListNode *pLast=head, *pCur=head->next, *pNext=NULL;
        head->next=NULL;
    
        while (pCur!=NULL)
        {
            pNext = pCur->next;
            pCur->next = pLast;
    
            pLast = pCur;
            pCur = pNext;
        }
        return pLast;
    }
     
    void reorderList(struct ListNode* head) 
    {
        if (head==NULL) return NULL;
        int i,len;
        struct ListNode *pCur=head;
        
        // get list length
        for(len=0; pCur; len++, pCur=pCur->next); 
        
        // divide list at (len+1)/2
        pCur=head;
        for(i=1; i<(len+1)/2 ; i++, pCur=pCur->next);
        
        struct ListNode *pLeft = head;
        struct ListNode *pRight = pCur->next;
        pCur->next = NULL;
        pRight = reverseList(pRight);
        
        
        // intersects two lists (left & rev(right) )
        struct ListNode *pLeftNext, *pRightNext;
        while (pLeft && pRight) {
            pLeftNext = pLeft->next;
            pRightNext = pRight->next;
            
            pLeft->next = pRight;
            pRight->next = pLeftNext;
            
            pLeft = pLeftNext;
            pRight = pRightNext;
        }
        
        return head;
    }
    

Log in to reply
 

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