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;
}
};
分析：
为了满足时间复杂度，想到归并排序，为了满足空间复杂度，想到在原链表上进行排序。
但是在原链表上进行排序碰到问题有点多，尤其是不知道怎么判断终止条件和什么时候交换。
睡了一觉就想出来了。
时间击败63%，空间击败72%，室友说会不会是一晚上换了案例。。。。
说实话我还有点懵懂。