Merge sort is well-suited for linked lists. Split the list in half by finding the midpoint with a slow-fast pointer technique.

Sort List

hard

Acceptance: 40%

Linked List

Sort a singly linked list in ascending order. Aim for O(n log n) time complexity. Return the head of the sorted list.

Example 1:

Input:head = [6,1,4,2]

Output:[1,2,4,6]

Example 2:

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

Output:[-3,0,1,5,9]

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}