Share My AC C++ with explanation


  • 0
    L
    class Solution {
    public:
        void reorderList(ListNode *head) {
            //divide the linked list into two part
            //one from head to mid point
            // one from midpoint to end
            //if there are 2 element, no need to reorder
            if(head == NULL || head->next == NULL || head->next->next == NULL) return;
            
            //define two pointers, ptr1s represents: pointer 1 step, ptr2s represents: pointer 2 steps
            //hence, when ptr2s reaches the end of the list, ptr1s is in the middle of linked list
            ListNode* ptr1s = head;
            ListNode* ptr2s = head;
            while(ptr1s && ptr2s && ptr2s->next && ptr2s->next){
                ptr1s = ptr1s->next;
                ptr2s = ptr2s->next->next;
            }
            //head for next 
            ListNode* midptr = new ListNode(0);
            midptr->next = ptr1s->next;
            ptr1s->next = NULL;
            //reset ptr1s
            ptr1s = head;
            
            //reverse the linked list from mid to end
            ListNode* cur = midptr->next;
            while(cur->next){
                ListNode* then = cur->next;
                cur->next = then->next;
                then->next = midptr->next;
                midptr->next = then;
            }
            //Assign the head of mid pointer to ptr2s
            ptr2s = midptr->next;
            //release the memory of the dummy pointer
            delete midptr;
            
            //Merge two list, like a 'Z' shape working
            ListNode* ptr1s_next_tmp = NULL;
            ListNode* ptr2s_next_tmp = NULL;
            while(ptr1s && ptr2s){
                ptr1s_next_tmp = ptr1s->next;
                ptr1s->next = ptr2s;
                ptr2s_next_tmp = ptr2s->next;
                ptr2s->next = ptr1s_next_tmp;
                ptr1s = ptr1s_next_tmp;
                ptr2s = ptr2s_next_tmp;
            }
        }
    };

Log in to reply
 

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