[ Leetcode ] 148. Sort List - Java

 

Given the head of a linked list, return the list after sorting it in ascending order.

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

 

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

 

Solution

 

 
 import java.util.*;
 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;
    }
 }
 

1. ListNode가 null이거나 1개인 경우는 그대로 리턴한다

2. 값을 다 빼고 내림차순으로 sort한다

3. 첫번째부터 채워서 ListNode를 만들어준다

 

대체 더 빠르게는 어떻게 하는거지... 좀더 고민해보기