148. 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: []

/**
 * 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 {
    static int[] arr, mergedArr;
    public ListNode sortList(ListNode head) {
        List<Integer> list = new ArrayList<>();
        ListNode node = head;

        if (head == null) {
            return null;
        }

        if (head.next == null) {
            return head;
        }


        while (node != null) {
            list.add(node.val);
            node = node.next;
        }

        arr = new int[list.size() + 1];
        mergedArr = new int[list.size()];

        for (int i = 0; i < list.size(); i++) {
            arr[i] = list.get(i);
        }

        mergeSort(0, list.size() - 1);

        System.out.println(Arrays.toString(mergedArr));

        ListNode nowNode = new ListNode(mergedArr[0]);
        ListNode ans = nowNode;

        for (int i = 0; i < mergedArr.length - 1; i++) {
            ListNode nextNode = new ListNode(mergedArr[i + 1]);
            nowNode.next = nextNode;
            nowNode = nextNode;
        }

        return ans;
    }

    // 1, 2,  3, 4
    // 0.        3
    // 0  1 / 2  3
    // 0
    
    public void mergeSort(int l, int r) {
        if (l == r) {
            return;
        }

        int mid = (l + r) / 2;
        mergeSort(l, mid);
        mergeSort(mid + 1, r);
        merge(l, mid, r);
    }

    // 0 0 1
    public void merge(int l, int mid, int r) {
        int left = l; // 0
        int right = mid + 1; // 1
        int idx = l; // 0

        while (left <= mid || right <= r) {
            // 오른쪽 포인터가 마지막에 도달한경우
            // 왼쪽 포인터가 중간 지점에 도달하지 못했거나, 오른쪽 포인터의 값이 왼쪽보다 크거나 같을 때..
            if (right > r || (left <= mid && arr[left] <= arr[right])) {
                mergedArr[idx++] = arr[left++];
            } else {
                mergedArr[idx++] = arr[right++];
            }
        }

        for (int i = l; i <= r; i++) {
            arr[i] = mergedArr[i];
        }
    }
}

// 주어진 연결리스트를 오름차순으로 정렬하여 반환하라.
// mergeSort를 활용하여 정렬해보자!
// l가 mid에 도달할 때 까지, mid+1 가 r에 도달할 때 까지