C++ 64ms O(n) time O(1) space solution


  • 0
    A
    class Solution {
    public:
        void reorderList(ListNode* head) {
            if (head == nullptr) return;
            ListNode* mid = findMidNode(head);
            mid = reverseList(mid);
            ListNode* tmp = head;
            while (tmp != nullptr) {
                //cout << tmp->val << endl;
                if (tmp->next == nullptr){
                    tmp->next = mid;
                    break;
                }
                else{
                    ListNode* tmp1 = tmp->next;
                    ListNode* tmp2 = mid->next;
                    tmp->next = mid;
                    mid->next = tmp1;
                    tmp = tmp1;
                    mid = tmp2;
                }
            }
        }
        // find mid node of the list 
        ListNode* findMidNode(ListNode* head){
            ListNode* slow = head;
            ListNode* fast = head;
            while (fast->next && fast->next->next){
                slow = slow->next;
                fast = fast->next->next;
            }
            fast = slow->next; slow->next = nullptr;
            return fast;
        }
        
        // reverse list
        ListNode* reverseList(ListNode* head) {
            if (head == nullptr) return head;
            ListNode* prev = head; 
            while (prev->next){
                ListNode* curr = prev->next;
                prev->next = curr->next;
                curr->next = head;
                head = curr;
            }
            return head;
        }
    };

Log in to reply
 

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