[LeetCode/Java] 148. Sort List

0. 문제

https://leetcode.com/problems/sort-list/?envType=study-plan-v2&envId=top-interview-150

1. 문제 설명

• linked list의 헤드가 주어질 때, 오름차순으로 정렬된 리스트를 반환하라.

2. 문제 풀이

2.1. 접근법 : 배열 정렬

• 정수 배열에 linked list의 원소를 담고 정렬을 한다.
• 코드

/**
 * 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) {
        int count = 0;
        ListNode temp = head;
        
        while(temp!=null){
            count++;
            temp = temp.next;
        }

        int[] arr = new int[count];
        temp = head;
        count = 0;

        while(temp!=null){
            arr[count++] = temp.val;
            temp = temp.next;
        }
        
        Arrays.sort(arr);
        temp = head;
        count = 0;
        while(temp!=null){
            temp.val = arr[count++];
            temp = temp.next;
        }
        return head;
    }
}

4. 결과