0148. Sort List

https://leetcode.com/problems/sort-list

Description

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 * 104].

• -105 <= Node.val <= 105

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

ac1: merge sort

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        // corner cases
        if (head == null || head.next == null) return head;
        // O(nlogn) merge sort, quick sort, heap sort. because of the nature of Linked List, quick sort and heap sort are not applicable because they require calling index.
        //  use merge sort

        // find mid node, 2 pointers
        ListNode mid = findMid(head);

        //divide 2 parts, head and second
        ListNode first = head;
        ListNode second = mid.next;
        mid.next = null;

        //recursive
        first = sortList(first);
        second = sortList(second);

        //conquer: merge 2 sorted parts, dummy node
        ListNode dummy = new ListNode(0);
        ListNode ranger = dummy;
        while (first != null && second != null) {
            if (first.val < second.val) {
                ranger.next = first;
                first = first.next;
            } else {
                ranger.next = second;
                second = second.next;
            }
            ranger = ranger.next;
        }
        if (first == null) ranger.next = second;
        else ranger.next = first;

        return dummy.next;
    }
    private ListNode findMid(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}