思路：

　　相信大家对数组的归并排序非常了解，不了解的可以自己百度。本博客只是对单链表的归并排序中的小细节进行阐述.

这个图，就是一种分治的方式，当递归到最底层时，对两个数进行排序，当回到上一层，其实就得到了，两个有序的序列，然后再对这两个序列进行排序并合并成一个新的序列。这样一层一层的重复相同的操作，就可以得到整个序列的排序！

 

重点：

　　对于来两个有序序列的合并，是这样合并的。

　　先申请一个局部的节点（相当于 表头 ）：然后，比较左右链表的最小值，谁最小就把谁拆下来，放在新的链表后面。值得注意的是：全过程只是申请了一个表头节点的内存。这一点在不计算递归所使用的内存的话，空间复杂度为O(1)

下面看图解：

　　　　　　

然后，注意一下代码中p的维护，因为p是新链表的尾指针！

代码：

struct ListNode {    int val;    ListNode *next;    ListNode(int x) : val(x), next(NULL) {}};class Solution {public:    ListNode *sortList(ListNode *head){        if (!head || !head->next) return head;        //空链表和只有一个元素的链表不需要排序        ListNode *p = head, *q = head->next;        //找到链表的中间位置        while (q&&q->next){        //快慢指针，注意必须前两步存在            p = p->next;            q = q->next->next;        }        ListNode *left = sortList(p->next);        //右链表        p->next = NULL;        //将其断开，为两个链表        ListNode *right = sortList(head);                return merge(left, right);    }    ListNode *merge(ListNode *left, ListNode *right)    {        ListNode dummy(0);        //申请一个假节点        ListNode *p = &dummy;        while (left&&right){            if (left->val < right->val){                p->next = left;                left = left->next;            }            else{                p->next = right;                right = right->next;            }            p = p->next;        }        if (left)p->next = left;        if (right)p->next = right;        return dummy.next;    }};