题解 | #单链表的排序#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

/**
 * 
 * @param head ListNode类 the head node
 * @return ListNode类
 */
本代码使用归并的思想,先使用快慢指针找到单链表的中点,将链表切割为两部分，将两个有序的子链表合并为一个有序的链表
struct ListNode* sortInList(struct ListNode* head ) {
    // write code here
	//当前链表为空或者只有一个结点，无需排序，直接返回
    if(head==NULL||head->next==NULL){
        return head;
    }
	//快慢指针找到单链表的中点
    struct ListNode *fast=head->next,*low=head;
    while (fast!=NULL&&fast->next!=NULL) {
        fast=fast->next->next;
        low=low->next;
    }
	//将链表分割为两个子链表
    struct ListNode *left=head,*right=low->next;
    low->next=NULL;
	//将链表一直划分到最小
    left=sortInList(left);
    right=sortInList(right);
    if(left==NULL){
        return right;
    }
    if(right==NULL){
        return left;
    }
	//设置新链表的头指针和尾指针
    struct ListNode *p,*q;
    if(left->val<right->val){
        p=left;
        q=p;
        left=left->next;       
    }else {
        p=right;
        q=p;
        right=right->next;
    }
	//合并两个有序链表
    while (left!=NULL&&right!=NULL) {
        if(left->val<right->val){
            q->next=left;
            left=left->next;
        }else{
            q->next=right;
            right=right->next;
        }
        q=q->next;
    }
	//连接剩余的结点
    if(left!=NULL){
        q->next=left;
    }
    if(right!=NULL){
        q->next=right;           
    }
    return p;    
}