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

  • 0

    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;
        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
        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.