Sort a linked list using insertion sort.
还是插入排序简单呀。
/** * 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 || head->next == NULL) { return head; } ListNode *cur = head->next; head->next = NULL; ListNode *prev = NULL; ListNode *target = NULL; ListNode *tmp = NULL; while (cur != NULL) { prev = NULL; target = head; while (target != NULL && target->val <= cur->val) { prev = target; target = target->next; } if (prev == NULL) { head = cur; } else { prev->next = cur; } tmp = cur->next; cur->next = target; cur = tmp; } return head; } };