每日一题——单链表排序（归并排序）

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
/**
 * 
 * @param head ListNode类 the head node
 * @return ListNode类
 */
struct ListNode* merge(struct ListNode* head1,struct ListNode*head2)    //合并有序链表
{
    if(head1 == NULL || head2 == NULL)    
        return head1 == NULL ? head2 : head1;
    struct ListNode* newHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* pre = newHead;
    while(head1 && head2)
    {
        if(head1->val <= head2->val)
        {
            pre->next = head1;
            head1 = head1->next;
        }
        else 
        {
            pre->next = head2;
            head2 = head2->next;
        }
        pre = pre->next;
    }
    pre->next = head1 == NULL ? head2 : head1;
    return newHead->next;
}
struct ListNode* sortInList(struct ListNode* head ) {
    if( head == NULL || head->next == NULL)   //如果链表没有或只有一个节点，则以及有序，直接返回原头结点
        return head;
    struct ListNode *mid, *left, *right;
    mid = head->next;
    left = head;
    right = head->next->next;   //相当于快慢指针已经进行了一次下滑
    while(right != NULL && right->next != NULL)   //当快指针还没有走到表尾
    {
        mid = mid->next;
        left = left->next;
        right = right->next->next;
    }
    left->next = NULL;    //从left位置断开链表，进行分治
    return merge(sortInList(head), sortInList(mid));  //进行递归，当分割为不可分割的单个节点时，进行合并，最后返回有序链表的头节点
}