二刷LeetCode--148. 排序链表(C++版本),必会题，思维题

思路，本题其实考察了两个点：合并链表、链表切分。首先从1开始，将链表切成一段一段，因为需要使用归并，所以下一次的切分长度应该是当前切分长度的二倍，每次切分，我们拿出两段，然后将第三段的开头赋值给一个指针，合并前面两段，下一次继续从第三段开始切分，然后继续合并。
trick:::链表设置虚拟头结点dummyhead，这样对链表来说，第一个元素就是dummyhead的next所对应的节点元素，而不是dummyhead所对应的节点元素。dummyhead位置所对应的元素是根本不存在的，这只是未来我们编写逻辑方便而出现的一个虚拟头结点。dummyhead就是索引为0的这个位置的元素的前一个节点。当我们有了dummyhead后，为链表添加一个元素，就不需要对头结点进行特殊处理了，只需要找到等待添加位置的前一个位置的节点，

/*** 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;}
};