My solution uses O(1) space and O(n) time!


  • 1
    P
    void reorderList(ListNode* head) {
        if (!head || !head->next || !head->next->next) return;
        ListNode *slow = head, *fast = head, *pre = nullptr, *tmp, *preSlow = nullptr;
        while (fast && fast->next) {
            preSlow = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        if (fast) {
            preSlow = slow;
            slow = slow->next;
        } 
        preSlow->next = nullptr;
        while (slow) {
            tmp = slow->next;
            slow->next = pre;
            pre = slow;
            slow = tmp;
        }
        while (pre) {
            tmp = head->next;
            head->next = pre;
            pre = pre->next;
            head->next->next = tmp;
            head = tmp;
        }
    }

Log in to reply
 

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