Clear C++ O(1) space solution


  • 0

    Suppose we have a list [1,2,3,4,5,6,7]

    Steps as follow:

    • Divide the list into front list: [1,2,3,4] and tail list: [5,6,7]
    • Reverse the tail list to [7,6,5]
    • Join front and tail list,
       1      ->2      ->3      ->4
         ->7       ->6      ->5
    
    • Result: [1,7,2,6,3,5,4]

    Code:

    class Solution {
    public:
        void reorderList(ListNode* head) {
            if(!head) return;
            ListNode* slow = head, *fast = head;
            ListNode* pre = new ListNode(0);
            pre->next = slow;
            while(fast && fast->next){
                pre = pre->next;
                slow = slow->next;
                fast = fast->next->next;
            }
            if(fast) slow = slow->next, pre = pre->next;
            pre->next = NULL;
            ListNode* cur, *next;
            pre = NULL, cur = slow;
            while(cur){
                next = cur->next;
                cur->next = pre;
                pre = cur;
                cur = next;
            }
            ListNode* h1 = head, *h2 = pre, *p1, *p2;
            while(h1 && h2){
                p1 = h1->next;
                p2 = h2->next;
                h1->next = h2;
                h2->next = p1;
                h1 = p1;
                h2 = p2;
            }
        }
    };
    

Log in to reply
 

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