題目

給你鏈表的頭結點 head ，請將其按 升序 排列并返回 排序后的鏈表 。

思路

當我們第一眼看見這道題時心中其實是有思路的，我們不想這是個鏈表就當它是一個整型數組。那么自然而然就會想到各種各樣的排序方法，第一眼看上去大部分想到的可能是把這個一分為變成兩個子數組再對子數組進行排序。這個想法同樣適用于鏈表只不過只分一次并不行我們需要將其分到徹底分不了也就是只剩一個節點或者干脆沒有節點可分。在分完后就好做了啊兩個節點還不好做升序排序嗎？再往上就算變成了一個鏈表也是個有序鏈表，兩個有序鏈表連接起來不也很好做嗎。所以這道題的主要就是我們需要想到先將其分開再組合也就是使用分治的思想。
同時這一樣也是一種排序方法也就是歸并排序只不過歸并排序不止可以通過分治來完成還可以使用迭代所以這道題同樣也有另外一個方法我就不再說了。無論是分治還是迭代最后完成的都是歸并排序，我們使用分治也就是自頂向下進行歸并排序。

代碼

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* sortList(ListNode* head) {// 歸并排序// 運用分治的思想// 將鏈表進行劃分直到為單個節點// 然后一個一個的連接起來return MergeSort(head, nullptr);}ListNode* MergeSort(ListNode* head, ListNode* tail) {// 直到只剩一個節點或者沒有節點if (head == nullptr) {return head;}if (head->next == tail) {head->next = nullptr;return head;}// 尋找中點進行劃分ListNode* cur = head;ListNode* prev = head;while (cur != tail && cur->next != tail) {cur = cur->next->next;prev = prev->next;}ListNode* mid = prev;return merge(MergeSort(head, mid), MergeSort(mid, tail));}ListNode* merge(ListNode* list1, ListNode* list2) {// 治也就是連接兩個鏈表// 哨兵節點，方便返回ListNode* newnode = new ListNode(0);ListNode* node = newnode;ListNode* node1 = list1;ListNode* node2 = list2;// 連接節點直到兩個鏈表有一個為空while (node1 != nullptr && node2 != nullptr) {if (node1->val < node2->val) {node->next = node1;node1 = node1->next;} else {node->next = node2;node2 = node2->next;}node = node->next;}// 由于先劃分到最底層一個一個節點// 再從一個一個節點組合成鏈表的// 所以兩個鏈表最多只會多一個節點if (node1 != nullptr) {node->next = node1;node1 = node1->next;node = node->next;}if (node2 != nullptr) {node->next = node2;node2 = node2->next;node = node->next;}return newnode->next;}
};