#include<iostream>
using namespace std;
//Sort a linked list in O(n log n) time using constant space complexity.
//Definition for singly-linked list.
//归并排序
#if 0
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
struct LinkList {
int size;
ListNode head;
};
class Solution {
public:
ListNode *sortList(ListNode *head) {
}
LinkList *PushElement(LinkList* linklist, int val) {
if (linklist->size == 0) {
return NULL;
}
ListNode* listnode = (ListNode*)malloc(sizeof(ListNode));
listnode = linklist->head.next;
listnode->val = val;
listnode->next = NULL;
linklist->size++;
return linklist;
}
int getTopElement(LinkList* linklist) {
if (linklist->size == 0) {
return 0;
}
ListNode* listnode = (ListNode*)malloc(sizeof(ListNode));
for (int i = 0; i < linklist->size; i++)
{
listnode = linklist->head.next;
}
return listnode->val;
}
};
#endif
#if 1
//Definition for singly-linked list.
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode *sortList(ListNode *head) {
if (head == NULL || head->next == NULL)
return head;
ListNode* slow = head;
ListNode* fast = head->next;
while (fast != NULL && fast->next != NULL && slow != NULL)
{
fast = fast->next->next;
slow = slow->next;
}
ListNode* left = sortList(slow->next);
slow->next = NULL;
ListNode* right = sortList(head);
return mergeTwoList(left, right);
}
ListNode *mergeTwoList(ListNode* left, ListNode *right)
{
ListNode* dummy = new ListNode(0);
ListNode* p = dummy;
while (left && right)
{
if (left->val > right->val)
{
p->next = right;
right = right->next;
}
else
{
p->next = left;
left = left->next;
}
p = p->next;
}
if (left == NULL)
p->next = right;
if (right == NULL)
p->next = left;
return dummy->next;
}
};
#endif
