单向链表的插入排序,本来很简单的题,写得跟屎一样。 是不是应该歇歇暂时不写leetcode了。明天就开题了。
class Solution { public: int GetCount(ListNode *head) { int count = 0; while(head != NULL) { count++; head=head->next; } return count; } ListNode *insertionSortList(ListNode *head) { if(head == NULL)return head; ListNode * now = head->next; ListNode * before = head; int count = GetCount(head); while(now != NULL) { ListNode * tmpnow = now->next; if(now->val <= head->val) { ListNode * tmp = now->next; before->next = now->next; now->next = head; head = now; now = tmpnow; } else { ListNode * beforetmp = head; ListNode * tmp = beforetmp->next; while(tmp != now && tmp->val <= now->val) { beforetmp = beforetmp->next; tmp = tmp->next; } if(tmp != now) { beforetmp->next = now; before->next = now->next; now->next = tmp; now = tmpnow; } else { before = now; now = tmpnow; } } } ListNode * chead = head; for(int i = 1;i < count;i++) { chead = chead->next; } chead->next = NULL; return head; } };