[Java] 148. Sort List

문제 파악

연결 리스트의 head가 주어진다.

 

오름차순으로 정렬해서 반환해야한다.

 

---

 

풀이

 

1️⃣ 배열과 mergeSort

💡 떠오른 Idea

O(NlogN) 방식으로 해결하기 위한 방법을 떠올려봤다.

해당 시간 복잡도로 정렬할 수 있는 Merge Sort 방식을 사용해야 해결할 수 있을 것이라 판단했다.

 

class Solution {
    public ListNode sortList(ListNode head) {
        int cnt = getCount(head);
        System.out.println(cnt);
        int[] arr = new int[cnt];
        ListNode dummyHead = new ListNode(0, head);

        ListNode node = head;
        for (int i = 0; i < cnt; i++) {
            arr[i] = node.val;
            node = node.next;
        }

        mergeSort(arr, 0, cnt);
        for (int i = 0; i < cnt; i++) {
            head.val = arr[i];
            head = head.next;
        }
        return dummyHead.next;
    }

    private int getCount(ListNode head) {
        int cnt = 0;
        while (head != null) {
            head = head.next;
            cnt++;
        }
        return cnt;
    }

    private void mergeSort(int[] arr, int left, int right) {
        if (right - left <= 1) {
            return;
        }
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid, right);
        merge(arr, left, mid, right);
    }

    private void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left];
        int idx = 0, l = left, r = mid;
        while (l < mid && r < right) {
            if (arr[l] > arr[r]) {
                temp[idx++] = arr[r++];
            } else {
                temp[idx++] = arr[l++];
            }
        }

        while (l < mid) {
            temp[idx++] = arr[l++];
        }

        while (r < right) {
            temp[idx++] = arr[r++];
        }

        for (int i = left; i < right; i++) {
            arr[i] = temp[i - left];
        }

    }
}

 

배열 mergeSort를 구현한 경험이 있어, Node 의 값을 배열에 옮겨서 mergeSort 를 하고 값을 갱신시켜주는 방식으로 진행하였다.

 

결과

이 방식의 단점은 배열을 선언함으로서 추가적인 메모리를 필요로 한다는 것이다.

 

 

---

📖 회고

추가적인 배열 생성없이 노드로만 구현하는 방법은 고민 중이다..

 

혼자서 3시간 정도는 구현해보려고 한 것 같은데 헷갈리는 부분이 많아서 쉽게 해결되지 않는다.

 

혼자 해결해보고 내용을 추가해봐야겠다.