冒泡排序：
struct ListNode* sortList(struct ListNode* head){
struct ListNode* pf = head;
struct ListNode* move = head;
struct ListNode* str = NULL;
int len = 1;
int temp = 0;
int i = 0;
int j = 0;
if( head == NULL || head->next == NULL )//这里将链表中只有一个元素或无元素，单独处理（其实只用写head == NULL）
return head;
for( ; move->next!= NULL;move = move->next)
{
for( pf = head ; pf->next!=str; pf = pf->next)
{
if( pf->val > (pf->next)->val )
{
temp = pf->val;
pf->val = (pf->next)->val;
(pf->next)->val = temp;
}
}
str = pf;
}
return head;
}
这种分法时间复杂度过高，通过不了
归并排序：
归并排序主要的思想是分而治之，递归
2 3 1 9 8 5 4 6 7
2 3 1 9 8 || 5 4 6 7
2 3 1 || 9 8 || 5 4 || 6 7
2 3 || 1 || 9 || 8 || 5 || 4 || 6 || 7
2 || 3 || 1 || 9 || 8 || 5 || 4 || 6 || 7
2 3 || 1 || 8 9 || 4 5 || 6 7
1 2 3 || 8 9 || 4 5 6 7
1 2 3 8 9 || 4 5 6 7
1 2 3 4 5 6 7 8 9
struct ListNode* merge(struct ListNode* l1,struct ListNode* l2 )
{
struct ListNode pf = { 0,NULL};
struct ListNode* arr = &pf;
struct ListNode* dummy = &pf;
while( l1 != NULL && l2 != NULL )
{
if( l1->val > l2->val )
{
dummy->next = l2;
l2 = l2->next;
}
else
{
dummy->next = l1;
l1 = l1->next;
}
dummy = dummy->next;
}
if( l1 != NULL )
{
dummy->next = l1;
}
if( l2 != NULL )
{
dummy->next = l2;
}
return arr->next ;
}
struct ListNode* cut( struct ListNode* head)
{
struct ListNode* fast = head->next;
struct ListNode* mid = NULL;
struct ListNode* slow = head;
while( fast != NULL && fast->next != NULL )
{
if( fast->next == NULL )
break;
fast = fast->next->next;
slow = slow->next;
}
mid = slow->next;
slow->next = NULL;
return mid;
}
struct ListNode* sortList(struct ListNode* head){
if( head == NULL || head->next == NULL )
{
return head;
}
struct ListNode* temp = cut(head);
struct ListNode* l1 = sortList(head);
struct ListNode* l2 = sortList(temp);
return merge(l1,l2);
}