A concise O(n) time, O(1) in place solution


  • 64
    S
    // O(N) time, O(1) space in total
    void reorderList(ListNode *head) {
        if (!head || !head->next) return;
        
        // find the middle node: O(n)
        ListNode *p1 = head, *p2 = head->next;
        while (p2 && p2->next) {
            p1 = p1->next;
            p2 = p2->next->next;
        }
        
        // cut from the middle and reverse the second half: O(n)
        ListNode *head2 = p1->next;
        p1->next = NULL;
        
        p2 = head2->next;
        head2->next = NULL;
        while (p2) {
            p1 = p2->next;
            p2->next = head2;
            head2 = p2;
            p2 = p1;
        }
        
        // merge two lists: O(n)
        for (p1 = head, p2 = head2; p1; ) {
            auto t = p1->next;
            p1 = p1->next = p2;
            p2 = t;
        }
        
        //for (p1 = head, p2 = head2; p2; ) {
        //    auto t = p1->next;
        //    p1->next = p2;
        //    p2 = p2->next;
        //    p1 = p1->next->next = t;
        //}
    }

  • 0
    L

    My code is almost the same with yours except the "Merge Two Lists" part. Your code is much more efficient! So concise!


  • 0
    L

    good idea!how nice solution!


  • 1
    K

    what an elegant solution!!!!!!!!!!!!!!!


  • 0
    O

    Thank you for your good sharing. Smarter than mine.


  • 0
    P

    so concise, so brief


  • 2
    C

    2 improvements needed to pass all test cases

    1. If list contains only 2 nodes, check the condition at the top and return. There is no need to process further.
      if(!head || !head->next || !head->next->next) return;

    2. For lists that contain even no of nodes. For example 1->4->3->2. Your solution returns 1->4->3. For the solution to work for this case I made the following change.
      ListNode *prev=NULL;
      for (p1 = head, p2 = head2; p1; ) {
      auto t = p1->next;
      prev=p1;
      p1 = p1->next = p2;
      p2 = t;
      }
      if(p2)
      {
      prev->next=p2;
      }


  • 0
    B

    @shichaotan your merging is cool...


Log in to reply
 

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