题解 | #单链表的排序#

题意思路：

给定一个无序单链表，实现单链表的排序(按升序排序)。

方法一:利用stl和sort排序
先新建一个vector，将单链表的元素存储于vector

sort排序从小到大

将vector变成单链表

复杂度分析

时间复杂度：O(NlogN)，N链表的长度，遍历链表，排序复杂度NlogN；

空间复杂度：O(N)，链表存储与读取数据

代码：

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

class Solution {
    static bool cmp(ListNode* a,ListNode* b){
        return a->val<b->val;
    }
public:
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */

    ListNode* sortInList(ListNode* head) {
        // write code here

        vector<ListNode*> node;//遍历链表元素所存储的vector
        ListNode* p=head;//从头指针遍历
        while(p){//若指针指向空则退出
            node.push_back(p);
            p=p->next;
        }

        sort(node.begin(),node.end(),cmp);//从小到大排序，注意cmp
        for(int i=0;i<node.size()-1;i++){//构建新链表
            node[i]->next=node[i+1];
        }
        node[node.size()-1]->next=NULL;
        return node[0];//返回头指针
    }


};

方法二:归并排序
归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法。

该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

若将两个有序表合并成一个有序表，称为二路归并。

复杂度分析

时间复杂度：O(NlogN)，N链表的长度，遍历链表，归并排序递归复杂度NlogN；

空间复杂度：O(1)，未开辟新空间

图解：

分而治之 递归处理

java代码：

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        // write code here
        if (head == null || head.next == null)//特判条件
            return head;

        ListNode i = head.next, j = head;
        while (i != null && i.next != null) {// 寻找链表的中点
            j = j.next;
            i = i.next.next;
        }
        ListNode tmp = j.next;//
        j.next = null;
        // 递归链表中点的左右两边
        ListNode l = sortInList(head);
        ListNode r = sortInList(tmp);
        ListNode h = new ListNode(0);
        ListNode res = h;//最后用链表存储结果
        // 合并 l，r两个链表
        while (l != null && r != null) {//左右链表都为空则退出
            //比较l和r链表中的大小
            if (l.val < r.val) {//从小到大排序
                h.next = l;
                l = l.next;
            } else {
                h.next = r;
                r = r.next;
            }
            h = h.next;
        }
        // 最后添加未对比的链表部分判断左链表是否为空
        if(l!=null){
            h.next=l;

        }else h.next=r;
        return res.next;
    }
}