My c++ solution for 【Reorder List】AC within 72ms


  • 6
    X
    class Solution {
    public:
        void reorderList(ListNode *head) {
    		if (!head) return;
    		ListNode dummy(-1);
    		dummy.next = head;
    		ListNode *p1 = &dummy, *p2 = &dummy;
    		for (; p2 && p2->next; p1 = p1->next, p2 = p2->next->next);
    		for ( ListNode *prev = p1, *curr = p1->next; curr && curr->next; ){
    			ListNode *tmp = curr->next;
    			curr->next = curr->next->next;
    			tmp->next = prev->next;
    			prev->next = tmp;
    		}
    		for ( p2 = p1->next, p1->next = NULL,p1 = head; p2; ){
    			ListNode *tmp = p1->next;
    			p1->next = p2;
    			p2 = p2->next;
    			p1->next->next = tmp;
    			p1 = tmp;
    		}
        }
    };
    

    Step1. get the mid Node of the list

    Step2. reverse the second half list

    Step3. merge the two half lists

    Clean & Concise is better


  • 0
    C

    your answer is brilliant ! you are very smart!


Log in to reply
 

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