下面图片中的这个内容要怎么做,我不会做,我该如何去解决它呢?
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
class Solution {
public:
ListNode* get_middle_position(ListNode* head,ListNode* tail)
{
ListNode* slow,*fast;
slow = head;
fast = head;
while(fast != tail && fast->next != tail)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
ListNode* merge(ListNode* left,ListNode* right)
{
ListNode *head, *cur;
if (left->val < right->val)
{
head = left;
left = left->next;
}
else
{
head = right;
right = right->next;
}
cur = head;
while (left && right)
{
if (left->val < right->val)
{
cur->next = left;
left = left->next;
cur = cur->next;
}
else
{
cur->next = right;
right = right->next;
cur = cur->next;
}
}
if (left)
{
cur->next = left;
}
if (right)
{
cur->next = right;
}
return head;
}
ListNode* MergeSort(ListNode* begin, ListNode* mid, ListNode* end)
{
if (begin->next == end)
{
begin->next = nullptr;
return begin;
}
return merge(MergeSort(begin, get_middle_position(begin, mid), mid), MergeSort(mid, get_middle_position(mid, end), end));
}
/**
*
* @param head ListNode类
* @return ListNode类
*/
ListNode* sortList(ListNode* head) {
// write code here
if(head == NULL)
return NULL;
return MergeSort(head,get_middle_position(head, NULL),NULL);
}
};