/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: You should return the head of the sorted linked list,
                    using constant space complexity.
     */
    ListNode *sortList(ListNode *head) {
        if (head == NULL) 
            return head;
        return quickSort(head);

    }

    ListNode* quickSort(ListNode *head) {
        if (head == NULL || head->next == NULL) {
            return head;
        }

        ListNode* slow = head;
        ListNode* fast = head->next;

        while (fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
        }

        int pivot = slow->val;

        ListNode* dummy1 = new ListNode(0);
        ListNode* dummy2 = new ListNode(0);
        ListNode* dummyPivot = new ListNode(0);

        ListNode* cur1 = dummy1;
        ListNode* cur2 = dummy2;
        ListNode* curPivot = dummyPivot;
        ListNode* cur = head;


        // Split original list into three parts: 1) < pivot; 2) == pivot; 3) > pivot;
        while (cur != NULL) {
            if (cur->val < pivot) {
                cur1->next = cur;
                cur1 = cur1->next;
            } else if (cur->val > pivot) {
                cur2->next = cur;
                cur2 = cur2->next;
            } else {
                curPivot->next = cur;
                curPivot = curPivot->next;
            }
            cur = cur->next;
        }

        cur1->next = NULL;
        cur2->next = NULL;

        ListNode* newHead1 = quickSort(dummy1->next);
        ListNode* newHead2 = quickSort(dummy2->next);

        ListNode* tail1 = newHead1;

        while (tail1 != NULL && tail1->next != NULL) {
            tail1 = tail1->next;
        }

        // Discuss if tail1 would be NULL; if pivot value happens to be the smallest across the whole list, newHead1 == NULL, tail1 == NULL; since there is no nodes having value smaller than pivot node and the list nodes with smaller than pivot value is empty;
        if (tail1 != NULL) {
            tail1->next = dummyPivot->next;
            curPivot->next = newHead2;
            return newHead1;
        } else {
            curPivot->next = newHead2;
            return dummyPivot->next;
        }
    }
};
//Merge Sort
class Solution {
public:
    /*
     * @param head: The head of linked list.
     * @return: You should return the head of the sorted linked list, using constant space complexity.
     */
    ListNode * sortList(ListNode * head) {
        // write your code here
        if (head == NULL || head->next == NULL) {
            return head;
        }
        ListNode* middle = findMiddle(head);
        ListNode* right = sortList(middle->next);
        middle->next = NULL;
        ListNode* left = sortList(head);
        return merge(left, right);
    }
    ListNode* findMiddle(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head->next;      
        while (fast !=NULL && fast->next !=NULL) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    ListNode* merge(ListNode* left, ListNode* right) {
        ListNode* dummy = new ListNode (0);
        ListNode* head = dummy;
        while (left != NULL && right != NULL) {
            if (left->val < right->val) {
                head->next = left;
                left = left->next;
            } else {
                head->next = right;
                right = right->next;
            }
            head = head->next;
        }
            if (left != NULL) {
                head->next = left;
                }    
                else if (right != NULL) {
                head->next = right;
            }
        return dummy->next;
    }
};