# 148. Sort List
Sort a linked list in O(n log n) time using constant space complexity.
Example 1:
Input: 4->2->1->3
Output: 1->2->3->4
Example 2:
Input: -1->5->3->4->0
Output: -1->0->3->4->5
# Solution
Approach 1: Merge sort.
# Code (Python)
Approach 1:
# Code (C++)
Approach 1:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
private:
ListNode* splitAndGetMidNode(ListNode* head) {
if (!head || !head->next)
return NULL;
ListNode *prev = NULL;
ListNode *slow = head;
ListNode *fast = head;
while (fast && fast->next)
{
prev = slow;
slow = slow->next;
fast = fast->next->next;
}
prev->next = NULL;
return slow;
}
ListNode* mergeSortList(ListNode* head1, ListNode* head2) {
if (head1 == NULL)
return head2;
if (head2 == NULL)
return head1;
ListNode *p1 = mergeSortList(head1, splitAndGetMidNode(head1));
ListNode *p2 = mergeSortList(head2, splitAndGetMidNode(head2));
ListNode dummyHead(0);
ListNode *p3 = &dummyHead;
while (p1 || p2)
{
if (!p2 || p1 && p1->val <= p2->val )
{
p3->next = p1;
p3 = p3->next;
p1 = p1->next;
}
else
{
p3->next = p2;
p3 = p3->next;
p2 = p2->next;
}
}
return dummyHead.next;
}
public:
ListNode* sortList(ListNode* head) {
return mergeSortList(head, splitAndGetMidNode(head));
}
};