题解 | #单链表的排序#

链表的排序一般有插入、冒泡、选择、快排等方式，今天就想自己实现一个，不参考任何其他的程序，一开始想的是按照冒泡排序吧，每轮找到一个最大的，然后把它放到尾巴，再让end指针往前移动，只要head!=end 没有重合，说明排序没有结束，那么继续 然后遇到的问题是，这个head是有数据的，不是一般所指的空的头指针，其次还有一个问题如果max指向的是最后一个位置怎么办，也需要特殊判断，这些都是后来测试的时候，调试遇到的错误 我觉得自己写慢慢查找问题是有好处的，因为我知道这个基本思路没错，那么问题就在于程序设计本身有小问题了，所以就不断调试，修改，下面是成功通过的程序，有些许冗余

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

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    ListNode* sortInList(ListNode* head) {
        // write code here
        //冒泡排序
        if(head->next==NULL)
            return head;
        ListNode *end=NULL;
        
        ListNode *max=NULL;
        ListNode *max_prior=NULL;
        ListNode *cur_prior=NULL;
        ListNode *cur=NULL;
        while(head!=end)//链表尚未走完
        {
            max_prior=head;
            cur_prior=head;
            for(max=head,cur=head->next;cur!=end;)
            {
                if(cur->val > max->val)
                {
                    max=cur;
                    max_prior=cur_prior;
                }
                cur_prior=cur;
                cur=cur->next;
            }
            //找到最大的max
            if(max->next==end)
                end=max;
            else if(max==head)
            {
                head=max->next;
                max->next=end;
                cur_prior->next=max;
                end=max;
            }
            else
            {
                max_prior->next=max->next;
                max->next=end;
                cur_prior->next=max;
                end=max;
            }
            
        }
        return head;
    }
};