sortlist.cpp

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
	ListNode* mergeTwoSortedList(ListNode* head1, ListNode* head2)
	{
		ListNode dummyNode(0);
		ListNode* dummy = &dummyNode;
		while (head1 != NULL && head2 != NULL) {
			if (head1->val < head2->val) {
				dummy->next = head1;
				head1 = head1->next;
			} else {
				dummy->next = head2;
				head2 = head2->next;
			}
			dummy = dummy->next;
		}

		if (head1 != NULL)
			dummy->next = head1;
		if (head2 != NULL)
			dummy->next = head2;

		return dummyNode.next;
	}

    ListNode* sortList(ListNode* head) {
        if (head == NULL)
        	return head;
        if (head->next == NULL)
        	return head;

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

        ListNode* newhead = slow->next;
        slow->next = NULL;

        return mergeTwoSortedList(sortList(head), sortList(newhead));

    }
};