Sort a linked list using insertion sort.
C++
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* insertionSortList(ListNode* head){ ListNode* newHead = new ListNode(-1); while (NULL != head){ ListNode* tmp = head->next; ListNode* cur = newHead; while(cur->next != NULL && cur->next->val < head->val){ cur = cur->next; } head->next = cur->next; cur->next = head; head = tmp; } return newHead->next; } };
转载于:https://www.cnblogs.com/vercont/p/10210282.html
