由于单向链表只能单方向遍历,因此不能像数组的插入排序那样。
在这里使用递归实现,其有一个断链和合链的过程,这是代码的关键所在。
class Solution { public: /** * * @param head ListNode类 * @return ListNode类 */ ListNode* insertionSortList(ListNode* head) { // write code here if (!head || !head->next) return head; ListNode dummyHead(0), *p; dummyHead.next = insertionSortList(head->next); p = &dummyHead; // 插入排序: 关键在于寻找插入位置 while (p && p->next && p->next->val < head->val) { p = p->next; } head->next = p->next; p->next = head; return dummyHead.next; } };