1 /** 2  * Definition for singly-linked list. 3  * struct ListNode { 4  *     int val; 5  *     ListNode *next; 6  *     ListNode(int x) : val(x), next(NULL) {} 7  * }; 8  */ 9 class Solution {10 public:11     ListNode* sortList(ListNode* head) {12         if (head == nullptr) return nullptr;13         if (head->next == nullptr) return head;14         int length = 0;15         ListNode* ptr = head;16         while (ptr != nullptr) {17             ++length;18             ptr = ptr->next;19         }20         return sortList(head, length);21     }22 private:23     ListNode* sortList(ListNode* head, int length)24     {25         if (length == 0) return nullptr;26         if (length == 1) return head;27         else {28             ListNode* rightHalf = head;29             ListNode* leftTail = nullptr;30             int count = length / 2;31             while (count--) {32                 leftTail = rightHalf;33                 rightHalf = rightHalf->next;34             }35             leftTail->next = nullptr; // 这里改变了原有链表的结构36             return mergeList(sortList(head, length / 2), sortList(rightHalf, length - length / 2));37         }38     }39     40     ListNode* mergeList(ListNode* ptr1, ListNode* ptr2) {41         ListNode dummy(-1);42         ListNode* ptr = &dummy;43         while (ptr1 && ptr2) {44             if (ptr1->val < ptr2->val) {45                 ptr->next = ptr1;46                 ptr1 = ptr1->next;47             }48             else {49                 ptr->next = ptr2;50                 ptr2 = ptr2->next;51             }52             ptr = ptr->next;53         }54         ptr->next = (ptr1 == nullptr) ? ptr2 : ptr1;55         return dummy.next;56     }57 };