My Cpp Answer, any way to optimize?


  • 0
    S
    void reorderList(ListNode *head) {
             ListNode *first = head, *middle = head, *tail = head, *pre_tail;
    
         if (head == NULL || head->next == NULL) { return;}
    
         pre_tail = middle;
         // find the middle node
         while (tail != NULL && tail->next != NULL) {
             pre_tail = middle;
             middle = middle->next;
             if (tail->next->next != NULL) {
                 tail = tail->next->next;
             } else {
                 tail = tail->next;
             }
         }
    
         //cout << "Middle val: " << middle->val << endl;
         // split the list into two: (first, middle), (middle, tail);
         // reverse (middle, tail)
         ListNode *prev = NULL, *current = middle, *next=middle->next;
         while (current != NULL) {
             current->next = prev;
             prev = current;
    
             current = next;
             if (next != NULL) {
                 next = next->next;
             }
         }
    
         ListNode *subHead = prev, *subNext = prev;
    
         current = head;
         while (current != NULL) {
             next = current->next;
    
             current->next = subHead;
             current = next;
    
             if (subHead != NULL) {
                 subNext = subHead->next;
                 subHead->next = next;
    
                 subHead = subNext;
             }
         }
    }

Log in to reply
 

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