思路，本題其實考察了兩個點：合并鏈表、鏈表切分。首先從1開始，將鏈表切成一段一段，因為需要使用歸并，所以下一次的切分長度應該是當前切分長度的二倍，每次切分，我們拿出兩段，然后將第三段的開頭賦值給一個指針，合并前面兩段，下一次繼續從第三段開始切分，然后繼續合并。

/*** 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) {// 定義虛擬頭節點，注意這里不是結構體指針類型ListNode dummyhead(0);// 指針處理，這里使用點而不是箭頭,虛擬頭節點之后的節點是頭節點dummyhead.next = head;int len = 0;ListNode *p = head;// 計算鏈表長度while(p){++len;p = p -> next;}// 開始切割鏈表，從短的開始逐漸合成長的// 注意size每次增加長度為之前的兩倍(左移一位)for(int size = 1;size < len;size <<= 1){ListNode *cur = dummyhead.next;ListNode *tail = &dummyhead;while(cur){// 切下來一段鏈表節點ListNode *left = cur;// right是下一段鏈表的初始節點ListNode *right = cut_list(left, size);// 從下一段鏈表開始，繼續切cur = cut_list(right, size);// 切分之后開始進行合并,比如首先合并left,right為首的這兩段tail -> next = merge(left, right);// 當下一個位置不為空的時候繼續進行游走，直到（合并好的鏈表的）末尾while(tail -> next){tail = tail -> next;}}}return dummyhead.next;}ListNode *cut_list(ListNode *head, int n){int size = n;ListNode *p = head;// 如果需要切的size是1，那么就不需要裁切，所以首先對size進行自減while(--size && p){p = p -> next;} // 如果走到頭了，就返回空if(p == nullptr)return nullptr;// 如果不為空，就把p節點之后的節點進行處理ListNode *next = p -> next;p -> next = nullptr;// 返回被切分的下一個節點的位置return next;}ListNode *merge(ListNode *l1, ListNode *l2){// 虛擬頭節點ListNode dummyhead(0);ListNode *p = &dummyhead;// 當二者都不為空的時候開始歸并while(l1 && l2){// 選擇較小的進行尾插if(l1 -> val <= l2 -> val){p -> next = l1;p = p -> next;// 尾插結束之后游標后移l1 = l1 -> next;}else{p -> next = l2;p = p -> next;// 尾插結束之后游標后移l2 = l2 -> next;}}if(l1)p -> next = l1;if(l2)p -> next = l2;// 因為是虛擬頭節點，所以返回第一個數據節點return dummyhead.next;}
};