143일 (148. Sort List) LinkedList, Sort

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]

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 * 10^4].
• -10^5 <= Node.val <= 10^5

 

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

 

 

- 접근방법

O(n logn)의 시간복잡도 내에 연결리스트를 직접 정렬할 자신은 없고 자바언어에 내장된 자료구조를 이것저것 써보면서 가장 시간이 적게 드는 경우를 찾았다.

 

1. 우선순위 큐 (41ms)

주어지는 head의 모든 값을 우선순위 큐에 넣고, 큐에서 오름차순으로 값을 뺀다.

오름차순으로 꺼내지는 값을 각각 대응되는 연결리스트의 ListNode에 입력.

 

2. ArrayList (13ms)

주어지는 head의 모든 값을 어레이리스트에 넣는다. 그리고 컬렉션을 정렬한다.

오름차순으로 꺼내지는 값을 각각 대응되는 연결리스트의 ListNode에 입력.

(연결리스트의 길이는 한번 순회하기 전까지 길이를 알 수 없으므로 어레이리스트는 초기 공간에 값을 넣다가, 추가 공간이 필요하게 되면 새로운 공간에 기존 값을 옮겨담으면서 확장)

 

3. 배열(8ms)

주어지는 head를 순회하며 ListNode들의 총 길이 n을 구한다.

n크기의 정수형 배열을 arr를 초기화한다.

정수형 배열 arr에 주어지는 head의 모든 값을 복사한다.

정수형 배열 arr를 정렬한다.

정렬된 정수형 배열 arr의 값을 각각 대응되는 head들의 값에 붙여넣는다.

 

 

- 코드 

/**
 * 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) {
        ListNode tempHead = head;
        int[] arr;
        int n = 0;

        while(tempHead != null) {
            tempHead = tempHead.next;
            n++;
        }

        arr = new int[n];
        tempHead = head;

        for(int i = 0; i < n; i++) {
            arr[i] = tempHead.val;
            tempHead = tempHead.next;
        }

        Arrays.sort(arr);
        tempHead = head;

        for(int temp : arr) {
            tempHead.val = temp;
            tempHead = tempHead.next;
        }

        return head;
    }
}

 

위 3번을 보면 ListNode 순회를 여러번 해야 ListNode.val들의 값을 동일한 크기의 정수형 배열에 옮겨담을 수 있기 때문에 시간이 오래걸릴 것 같지만, 정확한 공간을 모른채 ArrayList를 사용한다면 ArrayList가 가득 찼을때 새로운 공간에 계속 옮겨담아야하므로 비효율적이다. (초기 10개부터 1.5배씩 확장)

 

 

 

 

https://leetcode.com/problems/sort-list/

LeetCode - The World's Leading Online Programming Learning Platform