问题描述：Sort a linked list in O(n log n) time using constant space complexity.

O(n lgn)时间复杂度，O(1)空间复杂度。

　　：O(n lgn)时间复杂度的排序算法有几个（快排，归并，希尔，堆），但是O(1)空间复杂度就有一定的压力，只有快排，但是此题是基于链表的，我们还可以多一个选择就是归并排序。

 

　　上次是时基于数组的我们需要构建一个中间数组，所以空间复杂度O（n），但是由于链表的一些性质我们不需要另外构建一个链表，空间没有消耗，可以为O（1），所以此题都是选择归并排序。PS：好像参考的都是归并，没有找到基于快排的，以后再研究研究。

 

　　归并排序原理简单说及时：1，拆分；2，有序数组或者链表的合并。

　　有序链表的合并也简单介绍下：我们可以用两个“指针”分别指向两个链表的头部，如果其中一个比另一个小，移动小的那个链表的指针并把小结果放在返回链表中，反之也是这样；一直这样操作下去，直到有一个指针已经超过数组范围。这种方法的时间复杂度为O（m+n），m和n分为为两个链表的长度。（ps：上述博客有完全代买）；

　　然后就是实现过程：

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:    ListNode *sortList(ListNode *head) {           if (head == NULL || head->next == NULL)             return head;          ListNode* left = head;         ListNode* right = head->next;        ListNode* test = head->next->next;         while(test != NULL) {              left = right;              test = test->next;              right = right->next;              if(test != NULL)                 test = test->next;          }          left->next = NULL;          ListNode* head1 = sortList(head);          ListNode* head2 = sortList(right);         ListNode* merged_head=Merge(head1,head2);         return merged_head;    }        //合并两个有序链表    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)    {        if (pHead1 == NULL)            return pHead2;        if (pHead2 == NULL)            return pHead1;        ListNode *newListNode = NULL;  //一个遍历存结果，一个用于返回        ListNode *head = NULL;        if (pHead1->val <= pHead2->val){         //存头结点先进行一次判断            newListNode = head = pHead1;            pHead1 = pHead1->next;        }        else{            newListNode = head = pHead2;            pHead2 = pHead2->next;        }        while (pHead1 != NULL && pHead2!= NULL)          //两个都不为空是一直遍历下去        {            if (pHead1->val <= pHead2->val){                head ->next= pHead1;                head = head->next;                pHead1 = pHead1->next;            }            else{                head->next = pHead2;                head = head->next;                pHead2 = pHead2->next;            }        }        if (pHead2 == NULL){                             //有一个为空时，直接另外一个直至为空            head->next = pHead1;        }        if (pHead1 == NULL){            head->next = pHead2;        }        return newListNode;    } };