class Solution {

  public:

      void sort_list(ListNode* head1, ListNode* head2,int len)//在原链表上进行排序

      {

          ListNode* cur_node1 = head1;

          ListNode* cur_node2 = head1;

          while (cur_node2->next != head2)

              cur_node2 = cur_node2->next;

          if (cur_node1->val > cur_node2->next->val)//必须先让cur_node1->val小于head2-》val

          {

              int temp = cur_node1->val;

              cur_node1->val = cur_node2->next->val;

              cur_node2->next->val = temp;

          }

          while (len > )

          {

              while (cur_node1!= cur_node2->next && cur_node1->next->val < cur_node2->next->val)

                  cur_node1 = cur_node1->next;

              if (cur_node1 == cur_node2->next)//说明head2的链表都小于head1

                  return;

              else if(cur_node1 == cur_node2)//说明cur_node2->next后面没有统计，但是前面的都满足了

              {

                  cur_node2 = cur_node2->next;

                  len--;

              }

              else//要交换了

              {

                  ListNode* temp = cur_node2->next;

                  cur_node2->next = cur_node2->next->next;

                  temp->next = cur_node1->next;

                  cur_node1->next = temp;

                  len--;

              }

          }

      }

      ListNode* sort_List(ListNode* head, int len)//归并排序

      {

          if (len == )

              return NULL;

          if (len == )

              return head;

          ListNode* mid_node = head;

          for (int i = len / ; i > ; i--)

              mid_node = mid_node->next;

          ListNode* left = sort_List(head, len / );

          ListNode* right;

          if (len &  == )

          {

              right = sort_List(mid_node, len /  + );

              sort_list(left, right, len /  + );

          }

          else

          {

              right = sort_List(mid_node, len / );

              sort_list(left, right, len /  );

          }

          return left;

      }

      ListNode* sortList(ListNode* head) {//初试输入

          int len = ;

          ListNode* cur_node = head;

          while (cur_node != NULL)

          {

              len++;

              cur_node = cur_node->next;

          }

          ListNode* res = sort_List(head, len);

          return res;

      }

  };