C++ 64 ms - Using recursion to reverse and weave the linked list at the same time


  • 1
    O
    class Solution {
    public:
        void reorderList(ListNode* head) {
            
            if (head == NULL || head->next == NULL || head->next->next == NULL)
            {
                return;
            }
            
            ListNode *slow = head;
            ListNode *fast = head;
            
            // Find the mid point
            while (fast !=  NULL && fast->next != NULL)
            {
                slow = slow->next;
                fast = fast->next->next;
            }
            
            // Start weaving
            weave(head, slow);
        }
        
    private:
        ListNode* weave(ListNode* forward, ListNode* slow)
        {
            // Weaving starts when you hit end of the list
            if (slow->next == NULL)
            {
                return forward;
            }
            ListNode* tmp = weave(forward, slow->next);
            ListNode* tmp1 = slow->next;
            slow->next = tmp1->next;
            tmp1->next = tmp->next;
            tmp->next = tmp1;
            
            return tmp1->next;
        }
    };
    

Log in to reply
 

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