[LeetCode] 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]

 

 

 

 

 

내 생각

 

주어진 연결 리스트의 'head'를 오름차순 정렬 뒤 return 하는 문제!

리스트가 비어 있거나, 노드가 하나만 있는 경우에는 그대로 반환한다. (이미 정렬되어 있음)

내림차순으로 정렬한 뒤 뒤의 값을 앞으로 추가하였다! (오름차순을 쓰려면 .next로 뒤에 붙이면 됨)

 

 

내 코드

class Solution {
    public ListNode sortList(ListNode head) {
        // 예외 처리: 리스트가 비어있거나, 노드가 하나만 있는 경우
        if (head == null || head.next == null) {
            return head;
        }

        // 값을 저장할 연결 리스트
        List<Integer> list = new ArrayList<>();
        
        // 연결 리스트의 모든 값을 리스트에 저장
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }

        // 내림차순으로 정렬
        Collections.sort(list, Collections.reverseOrder());

        // 정렬된 값으로 새로운 연결 리스트를 생성
        // 첫 번째 값으로 새로운 노드 생성
        ListNode answer = new ListNode(list.get(0));
        
        // 리스트의 나머지 값으로 연결 리스트를 생성
        for (int i = 1; i < list.size(); i++) {
            // 새 노드를 현재 노드 앞에 추가하여 역순으로 연결 리스트를 구성
            answer = new ListNode(list.get(i), answer);
        }

        // 정렬된 연결 리스트 반환
        return answer;
    }
}