简单来说就是给你一个链表,每个节点都有一个相应的value,按照value的大小对其进行排序。
由于是链表,所以可能选择插入排序是更为合理的选择,但是正真写起来发现处理逻辑过于复杂,此时选择使用
归并排序可能是更好的选择。
将一个列表分为两个列表,对两个列表再进行排序,再进行链表的合并
code
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
| class Solution { public: ListNode* sortList(ListNode* head) { if (head==NULL||head->next == NULL) return head; ListNode* slow = head ,*fast = head->next; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } fast = slow->next; slow->next = NULL; return merge(sortList(head), sortList(fast)); } ListNode *merge(ListNode*l1, ListNode*l2) { ListNode dump(0); ListNode *cur = &dump; while (l1 && l2) { if (l1->val < l2->val) { cur->next = l1; l1 = l1->next; } else { cur->next = l2; l2 = l2->next; } cur = cur->next; } if (l1) cur->next = l1; if (l2) cur->next = l2; return dump.next; } };
|