Share my accepted c++ solution,any better idea?


  • 0
    W

    step 1:divide list into 2 parts from mid.

    2:reverse second list

    3:insert second into first every other node
    done!

    void reorderList(ListNode *head) {
        if(head == NULL)
        {
            return;
        }
        
        ListNode *first=head;
        ListNode *second=head;
        
        while(second!=NULL && second->next!=NULL)
        {
            first=first->next;
            second=second->next->next;
        }
        
        second=first->next;
        first->next=NULL;
        first=head;
        reverse(&second);
        
        ListNode *tmp=NULL;
        //将second间隔插入first
        while(second!=NULL)
        {
            tmp=first->next;
            first->next=second;
            
            second=second->next;
            first->next->next=tmp;
            first=tmp;
        }
    }
    
    void reverse(ListNode **pNode)
    {
        if(pNode == NULL)
        {
            return;
        }
        ListNode *pPre=NULL;
        ListNode *pCur=*pNode;
        ListNode *pNext=NULL;
        
        while(pCur!=NULL)
        {
            pNext=pCur->next;
            if(pNext == NULL)
            {
                *pNode=pCur;
            }
            pCur->next=pPre;
            pPre=pCur;
            pCur=pNext;
        }
    }

  • 0
    S

    this is an O(N) time, O(1) space solution, i think it is the best solution


Log in to reply
 

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