Sort a linked list using insertion sort.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | /** * 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 * curi = head, * curj = head; ListNode dummy(INT_MIN); dummy.next = NULL; while(curi != NULL){ curj = &dummy; ListNode * node = curi; curi = curi->next; while(curj != NULL){ if(curj->next == NULL || curj->val<= node->val && curj->next->val > node->val){ ListNode * tmp = curj->next; curj->next = node; node->next = tmp; break; } curj = curj->next; } } return dummy.next; }}; |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | /** * 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) { if(head == NULL) return head; vector<int> list; ListNode * h = head; while(h != NULL){ list.push_back(h->val); h = h->next; } sort(list.begin(), list.end()); h = head; for(auto val: list){ h->val = val; h = h->next; } return head; }}; |
原文：http://www.cnblogs.com/zhxshseu/p/dad1866a95b38dcae0414c24f4c185cb.html