My C++ code (split, reverse the second half, and merge), 71 ms


  • 7
    D

    The basic idea is to split the list in half, then reverse the second half, and at last merge them. It is O(n) time, O(1) space. I was also wondering if there is a better solution.

    class Solution {
    public:
        void reorderList(ListNode *head) {
      // use fast/slow points to find the second half of the list       
                ListNode *head1, *head2;
                ListNode *preNode, *curNode;
                
                if(!head || !(head->next) )
                {// if the list is empty or only has one element
                    return;
                }
                else
                {
                    head1 = head;
                    head2 = head->next;
                    
                    // find the starting point of the second half
                    while(head2 && head2->next)
                    {
                        head1 = head1->next;
                        head2 = (head2->next)->next;
                    }
                    
                    //reverse the second half
                    head2 =head1->next; // the head of the second half
                    head1->next =NULL;
                    preNode = NULL;
                    
                    while(head2)
                    {
                        curNode = head2->next;
                        head2->next = preNode;
                        preNode= head2;
                        head2 = curNode;
                    }
                    
                    // merge the first half and the reversed second half
                    head2 = preNode;
                    head1 = head;
                    
                    while(head2)
                    {
                        curNode = head1->next;
                        head1 = head1->next = head2;
                        head2 = curNode;
                    }
                    
                    return;
                }
            }

  • 0
    N

    while(head2)
    {
    curNode = head1->next;
    head1 = head1->next = head2;
    head2 = curNode;
    }
    I am not able to understand the above code. Can someone help me out?


  • 1
    P

    @Narnian
    please read & execute the below snippet actually I just transformed the above one into your readable code
    curNode = head1->next;
    head1->next = head2;
    head1 = head1->next;
    head2 = curNode;


Log in to reply
 

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