链表排序

/**
* 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) {
// if (head == NULL || head->next == NULL) return head;
//
// ListNode* head1 = head;
// ListNode* head2 = split(head);
//
// head1 = sortList(head1);
// head2 = sortList(head2);
//
// return merge(head1, head2);
// }
// ListNode* split(ListNode* head) // 找链表的中间值；
// {
// ListNode* slow = head, * fast = head->next;
// while (fast != NULL && fast->next != NULL)
// {
// slow = slow->next;
// fast = fast->next->next;
// }
// ListNode* mid = slow->next;
// slow->next = NULL;
// return mid;
// }
// ListNode* merge(ListNode* head1, ListNode* head2)//合并两个链表
// {
// ListNode* dummy = new ListNode(0), * p = dummy;
// while (head1 != NULL && head2 != NULL) {
// if (head1->val < head2->val) {
// p = p->next = head1;
// head1 = head1->next;
// }
// else
// {
// p = p->next = head2;
// head2 = head2->next;
// }
// }
// if (head1 == NULL) p->next = head2;
// if (head2 == NULL) p->next = head1;
//
// return dummy->next;
// }
//};