算法思想很简单,就是进行插入排序
分为两个链表,head 代表了未排序链表的首部,rhs 代表已排序链表的首部。因此循环一直到 head == nullptr 为止。每次将 head 取出,然后从 rhs 中找一个合适的位置将其插入
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ class Solution { public: /** * * @param head ListNode类 the head node * @return ListNode类 */ ListNode* sortInList(ListNode* head) { ListNode* rhs = head; head = head->next; if(!head) return rhs; rhs->next = nullptr; while(head){ auto pos = rhs; while(pos->next &&(head->val > pos->next->val) ) pos = pos->next; auto tmp = head; head = head->next; if(tmp->val < rhs->val){ tmp->next = rhs; rhs = tmp; continue; } tmp->next = pos->next; pos->next = tmp; } return rhs; } };