题目描述：

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4
Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

题目要求算法复杂度是O(nlogn)，故不能使用冒泡和插入排序，因为是链表不能随机寻址，所以只能使用归并排序。

链表有两个基本操作需要先实现，拆分(split)和合并(merge), 用这两个基本操作就可实现算法。

拆分（split）: 给一个head和n, 拆成n个元素的左链表，剩下为右链表，返回右链表
如：1->2->3, 1; 返回2->3;

合并(merge): 给两个链表，按从小到大的顺序合并成一个链表，并返回
如：1->3, 2->4; 1->2->3->4;

则题目所给4->2->1->3, 先拆成4,2,1,3, 然后归并2->4, 1->3, 1->2->3->4

因为题目又要求只能用常量空间，所以不能开额外的容器存拆出来的元素，对编码技巧有一定要求。

代码

  ListNode* merge(ListNode* l1, ListNode* l2) {
    ListNode dummyHead(0);
    ListNode* p = &dummyHead;
    while (l1 && l2) {
      if (l1->val < l2->val) {
        p->next = l1;
        l1 = l1->next;
      } else {
        p->next = l2;
        l2 = l2->next;
      }
      p = p->next;
    }
    p->next = l1 ? l1 : l2;

    return dummyHead.next;
  }

  ListNode* split(ListNode* head, int n) {
    ListNode dummyNode(0);
    auto p = &dummyNode;
    int len = 0;
    auto pre = head;
    while(head && len <= n) {
      if (len == n) { p->next = head;
        pre->next = NULL;
        break;
      }
      pre = head;
      head = head->next;
      len++;
    }
    return dummyNode.next;
  }

  ListNode* sortList(ListNode* head) {
    int len = 0;
    ListNode* p = head;
    while(p) {
      p = p->next;
      len++;
    }

    ListNode dummyHead(0);
    dummyHead.next = head;
    for(int size = 1; size <= len; size <<= 1) {
      auto cur = dummyHead.next;
      auto tail = &dummyHead;
      while (cur) {
        auto left = cur;
        auto right = split(left, size);
        cur = split(right, size);
        tail->next = merge(left, right);
        while(tail->next) tail = tail->next;
      }
    }
    return dummyHead.next;
  }