My O(n) C++ Method, accepted


  • 13
    L

    Firstly, I split the list from the middle into two lists. One from head to middle, and the other from middle to the end. Then we reverse the second list. Finally we merge these two lists. O(n) time complexity and O(1) space complexity.

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        void reorderList(ListNode *head) {
            if(head == NULL || head->next == NULL || head->next->next==NULL)
                return;
            //find the middle of the list, and split into two lists.    
            ListNode *p=head,*q=head;
            while(p && q && q->next && q->next->next){
                p=p->next;
                q=q->next->next;
            }
            
            ListNode *mid = p->next;
            p->next=NULL;
            p=head;
            //reverse from the middle to the end
            ListNode *q1=mid, *q2,*q3;
            if(mid->next){
                q1=mid;
                q2=mid->next;
                while(q2){
                    q3=q2->next;
                    q2->next=q1;
                    q1=q2;
                    q2=q3;
                    
                }
                mid->next=NULL;
            }
            q=q1;
            //merge these two list
            ListNode *s=p;
            p=p->next;
            while(p && q){
               s->next=q;
               s=s->next;
               q=q->next;
               
               s->next=p;
               s=s->next;
               p=p->next;
            }
            if(p){
                s->next=p;
            }
            if(q){
                s->next=q;
            }
        }
    };

  • 1
    S

    I do like the code block:

           while(p && q && q->next && q->next->next){
            p=p->next;
            q=q->next->next;
        }
    

    I remember one of company has asked such a question,can you find the middle node in the list without using any other variables?And this code can solve this question, and what's more,it's quite fast!!!


  • 0
    P

    start p and q at head and p works as mid point?


  • 0
    S

    Yeah.i'm new about programming.So i feel really cool about using such way to make what we want....


  • 0
    C

    I guess (q && q->next) is enough.


  • 0
    S

    yeah ,u r right.That's enought


  • 0
    F

    @sjlxd But in this case p and q are also extra variables, aren't they?


  • 0
    P

    @for_the_glory I guess the context is "using a variable to count the number of nodes"


  • 0
    C

    I can't understand your code ! please tell me why.


Log in to reply
 

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