C++ 60ms straight forward solution without using extra space


  • 0
    B

    three steps:

    1. find break point
    2. reverse rear section
    3. insert rear section to front section
    class Solution {
    public:
        void reorderList(ListNode* head) 
        {
            if(!head) return;
            ListNode * fast = head;
            ListNode * slow = head;
            //find break point
            while(fast && fast -> next)
            {
                fast = fast -> next -> next;
                slow = slow -> next;
            }
            if(!slow->next) return;
            //reverse rear section
            fast = slow->next;
            while(fast->next)
            {
                ListNode * temp = fast -> next;
                fast -> next = temp -> next;
                temp -> next = slow -> next;
                slow -> next = temp;
            }
            //insert rear section to front section
            fast = head;
            while(slow->next)
            {
                ListNode * temp = slow -> next;
                slow -> next = temp -> next;
                temp -> next = fast -> next;
                fast -> next = temp;
                fast = fast -> next -> next;
            }
        }
    };

Log in to reply
 

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