leecode第一百四十八题（排序链表）

 

class Solution {public:void sort_list(ListNode* head1, ListNode* head2,int len)//在原链表上进行排序 {ListNode* cur_node1 = head1;ListNode* cur_node2 = head1;while (cur_node2->next != head2)cur_node2 = cur_node2->next;if (cur_node1->val > cur_node2->next->val)//必须先让cur_node1->val小于head2-》val {int temp = cur_node1->val;cur_node1->val = cur_node2->next->val;cur_node2->next->val = temp;}while (len > 0){while (cur_node1!= cur_node2->next && cur_node1->next->val < cur_node2->next->val)cur_node1 = cur_node1->next;if (cur_node1 == cur_node2->next)//说明head2的链表都小于head1return;else if(cur_node1 == cur_node2)//说明cur_node2->next后面没有统计，但是前面的都满足了 {cur_node2 = cur_node2->next;len--;}else//要交换了 {ListNode* temp = cur_node2->next;cur_node2->next = cur_node2->next->next;temp->next = cur_node1->next;cur_node1->next = temp;len--;}}}ListNode* sort_List(ListNode* head, int len)//归并排序 {if (len == 0)return NULL;if (len == 1)return head;ListNode* mid_node = head;for (int i = len / 2; i > 0; i--)mid_node = mid_node->next;ListNode* left = sort_List(head, len / 2);ListNode* right;if (len & 1 == 1){right = sort_List(mid_node, len / 2 + 1);sort_list(left, right, len / 2 + 1);}else{right = sort_List(mid_node, len / 2);sort_list(left, right, len / 2 );}return left;}ListNode* sortList(ListNode* head) {//初试输入int len = 0;ListNode* cur_node = head;while (cur_node != NULL){len++;cur_node = cur_node->next;}ListNode* res = sort_List(head, len);return res;}};

 分析：

为了满足时间复杂度，想到归并排序，为了满足空间复杂度，想到在原链表上进行排序。

但是在原链表上进行排序碰到问题有点多，尤其是不知道怎么判断终止条件和什么时候交换。

睡了一觉就想出来了。

时间击败63%，空间击败72%，室友说会不会是一晚上换了案例。。。。

说实话我还有点懵懂。

转载于:https://www.cnblogs.com/CJT-blog/p/10715147.html

总结

以上是生活随笔为你收集整理的leecode第一百四十八题（排序链表）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。