[LeetNode]Sort List

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode(int x) : val(x), next(NULL) {}

 * };

 */

class Solution {

private:

    int getlen(ListNode *head)

    {

        ListNode *p=head;

        int len=0;

        while(p)

        {

            len++;

            p=p->next;

        }

        return len;

    }

    ListNode* merge(ListNode *head1,ListNode *head2)

    {

        ListNode *p=head1,*q=head2,*head=NULL,*cur=NULL;

        while(p&&q)

        {

            if(p->val<=q->val)

            {

                if(head==NULL) head=cur=p;

                else 

                {

                    cur->next=p;

                    cur=p;

                }

                p=p->next;

            }

            else

            {

                if(head==NULL) head=cur=q;

                else 

                {

                    cur->next=q;

                    cur=q;

                }

                q=q->next;

            }

        }

        if(p) cur->next=p;

        if(q) cur->next=q;

        return head;

    }

public:

    ListNode *sortList(ListNode *head) {

        int len=getlen(head);

        if(len==0||len==1) return head;

        ListNode *p,*q,*r;

        p=r=head;

        int halflen=len>>1;

        for(int i=0;i<halflen-1;i++) r=r->next;

        q=r->next;

        r->next=NULL;

        p=sortList(p);

        q=sortList(q);

        ListNode *newhead=merge(p,q);

        return newhead;

    }

};