和数组里面的归并排序相同，用两个指针分别对应low high，递归进行归并排序然后merge把两个链表合在一起
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
ListNode* mergeSort(ListNode* head)
{
if (head->next == NULL)
return head;
ListNode* slow;
ListNode* fast;
slow = head;
fast = head;
while (fast->next&&fast->next->next)
{
slow = slow->next;
fast = fast->next->next;
}
ListNode* p;
p = slow->next;
slow->next = NULL;
ListNode* m;
ListNode* n;
m = mergeSort(head);
n = mergeSort(p);
return merge(m, n);
}
ListNode* merge(ListNode* p, ListNode* q)
{
ListNode* dummyNode;
dummyNode = new ListNode();
ListNode* pre;
pre = dummyNode;
while (p&&q)
{
if (p->val <= q->val)
{
pre->next = new ListNode(p->val);
pre = pre->next;
p = p->next;
}
else
{
pre->next = new ListNode(q->val);
pre = pre->next;
q = q->next;
}
}
while (p)
{
pre->next = new ListNode(p->val);
pre = pre->next;
p = p->next;
}
while (q)
{
pre->next = new ListNode(q->val);
pre = pre->next;
q = q->next;
}
ListNode* res;
res = dummyNode->next;
delete dummyNode;
return res;
}
public:
ListNode* sortList(ListNode* head) {
if (head == NULL)
return NULL;
return mergeSort(head);
}
};