题解 | NO.12#单链表的排序#3.6
单链表的排序
https://www.nowcoder.com/practice/f23604257af94d939848729b1a5cda08
/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 the head node * @return ListNode类 */ ListNode* merge(ListNode *head1, ListNode *head2){ //一个空了,直接返回另一个 if(head1 == NULL) return head2; if(head2 == NULL) return head1; //两链表都不空 ListNode *head = new ListNode(0); //设置哨兵结点 ListNode *temp = head; while(head1 && head2){ if(head1->val <= head2->val){ temp->next = head1; head1 = head1->next; }else{ temp->next = head2; head2 = head2->next; } //指针后移 temp = temp->next; } if(head1) temp->next = head1; if(head2) temp->next = head2; return head->next; } ListNode* sortInList(ListNode* head) { // 采用分而治之的思想,用归并排序 if(head == NULL || head->next == NULL) //忘了这一步,这是递归出口,非常重要 return head; ListNode* left = head; ListNode* mid = head->next; ListNode* right = head->next->next; //用快慢指针找中点 while(right != NULL && right->next != NULL){ left = left->next; mid = mid->next; right = right->next->next; } //左边指针指向左段的最后一个结点,从这里后边断开 left->next = NULL; //分成两段排序,合并排好序的两段 return merge(sortInList(head),sortInList(mid)); } };