?

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第一百四十八题（排序链表）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。