题目描述
对一个单链表原地（in-place）排序。即直接对链表结点排序。返回排序后链表的头结点。
链表结点的定义为（请不要在代码中再次定义该结构）：
C/C++struct ListNode {
int val;
ListNode *next;
}渣做法！N^2
ListNode* insert(ListNode* head, ListNode* item) {
if (item == NULL) return head;
if (head == NULL) { item->next = NULL; return item; }
if (item->val < head->val) { item->next = head; return item;}
ListNode* prev = head, *cur = head->next;
while (cur != NULL) {
if (cur->val < item->val) prev = cur, cur = cur->next;
else {
prev->next = item;
item->next = cur;
return head;
}
}
if (cur == NULL) {
prev->next = item;
item->next = NULL;
}
return head;
}
ListNode* sortLinkList(ListNode *head) {
if (!head) return head;
ListNode *cur = head, *newhead = NULL, *next;
while (cur != NULL) {
next = cur->next;
newhead = insert(newhead, cur);
cur = next;
}
return newhead;
}