[Divide & Conquer]Sort List

목록 정렬

Sort List - LeetCode

head연결리스트의 경우 오름차순 으로 정렬한 후 목록을 반환합니다 .

 

예시 1:

입력: 헤드 = [4,2,1,3]
 출력: [1,2,3,4]

예 2:

입력: 헤드 = [-1,5,3,4,0]
 출력: [-1,0,3,4,5]

예시 3:

입력: 헤드 = []
 출력: []

 

제약:

• 목록의 노드 수가 범위 내에 있습니다 .[0, 5 * 10^4]
• -10^5 <= Node.val <= 10^5

---

문제풀이

/**
 * 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 {
    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;
    }
 }

• list에 head부터 head.next를 순회하여 head가 null까지 값을 list에 저장합니다
• Collerctions.sort()와Collerctions.sort()을 사용하여 내림차순으로 정렬하였습니다.
• 리스트를 순회하며 정렬된 새로운 노드를 만듭니다.