LeetCode-148. Sort List Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.https://leetcode.com/problems/sort-list/

Given the head of a linked list, return the list after sorting it in ascending order.

Example 1:

Input: head = [4,2,1,3]
Output: [1,2,3,4]

Example 2:

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

Example 3:

Input: head = []
Output: []

Constraints:

• The number of nodes in the list is in the range [0, 5 * 10^4].
• -10^5 <= Node.val <= 10^5

Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

【C++】

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(!head || !head->next) {return head;}  
        ListNode *mid = nullptr, *slow = head, *fast = head;
        while(fast && fast->next) {
            mid = slow;
            slow = slow->next;
            fast = fast->next->next;  
        }   
        mid->next = nullptr;            
        ListNode* l1 = sortList(head);    
        ListNode* l2 = sortList(slow);    
        return mergelist(l1, l2);   
    }
 
    ListNode* mergelist(ListNode *l1, ListNode *l2) {
        ListNode *dummy = new ListNode(0), *curr = dummy;
        while (l1 && l2) {
            if (l1->val > l2->val) {
                curr->next = l2;
                l2 = l2->next;
            } else {
                curr->next = l1;
                l1 = l1->next;
            }
            curr = curr->next;
        } 
        if(l1) {
            curr->next = l1;
            l1 = l1->next;
        }
        if(l2) {
            curr->next = l2;
            l2 = l2->next;
        }
        return dummy->next;
    }
};

【Java】

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) {return head;}  
        ListNode mid = null, slow = head, fast = head;
        while (fast != null && fast.next != null) {
            mid = slow;
            slow = slow.next;
            fast = fast.next.next;  
        }   
        mid.next = null;            
        ListNode l1 = sortList(head);    
        ListNode l2 = sortList(slow);    
        return mergelist(l1, l2);   
    }
 
    ListNode mergelist(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0), curr = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val > l2.val) {
                curr.next = l2;
                l2 = l2.next;
            } else {
                curr.next = l1;
                l1 = l1.next;
            }
            curr = curr.next;
        } 
        if(l1 != null) {
            curr.next = l1;
            l1 = l1.next;
        }
        if(l2 != null) {
            curr.next = l2;
            l2 = l2.next;
        }
        return dummy.next;
    }
}