C++ implementation: I am a fan of using vector


  • 0
    T
    class Solution {
    private:
        int NumList(ListNode* head)
        {
            ListNode* p = head;
            int n = 0;
            while(p != NULL)
            {
                n = n + 1;
                p = p->next;
            }
            return n;
        }
    public:
        void reorderList(ListNode* head) {
            int n = NumList(head);
            if(n<2)
                return;
                
            vector<ListNode*> pointer;
            pointer.resize(n);
            int i;
            ListNode* p;
            p = head;
            for(i=0; i<n; i++)
            {
                pointer[i] = p;
                p = p->next;
            }
    
            if(n%2==0)
            {
                for(i=0; i<n/2; i++)
                {
                    pointer[i]->next = pointer[n-1-i];
                    if(i <n/2-1)
                        pointer[n-1-i]->next = pointer[i+1];
                    else
                        pointer[n-1-i]->next = NULL;
                }
            }
            else
            {
                for(i=0; i<n/2; i++)
                {
                    pointer[i]->next = pointer[n-1-i];
                    pointer[n-1-i]->next = pointer[i+1];
                } 
                pointer[i]->next = NULL;
            }
    
        }
    };

Log in to reply
 

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