[Java Script]LeetCode 148. Sort List

1. 문제 개요

문제 링크 : 148. Sort List

Sort List - LeetCode

• 주어진 링크드 리스트 내의 값을 오름차순으로 정렬하여 반환해 주면 되는 문제입니다.

2. 문제 풀이

문제 해결을 위해서 링크드 리스트의 노드 주소값을 변경하는 작업은 매우 복잡하기 때문에

먼저 주어진 링크드 리스트의 모든 값을 추출하여 배열에 넣어줍니다.

이후 배열을 정렬하고 링크드 리스트를 처음부터 탐색하며 해당값을 정렬한 배열의 값으로 대체해 주는 방법으로

구현해 보겠습니다

 

주석으로 구현할 구조를 짜보겠습니다

var sortList = function(head) {
	// 주어진 링크드 리스트의 주소값 저장
    // 값을 정렬할 배열 정의
	// 링크드 리스트의 값을 추출하여 배열에 삽입
    // 배열을 정렬
    // 이후 링크드 리스트를 순서대로 돌면서 값을 삽입     
};

 

LeetCode 요구 양식으로 코드 구현

var sortList = function(head) {
    let headF = head;
    let data = [];

    let node = head;

    while (node) {
        data.push(node.val)
        node = node.next
    }

    data.sort(function (a,b){return a-b});
    
    let i = 0;
    while(head){
        head.val = data[i];
        head = head.next;          
        i++
    }
        
    return headF        
};

 

LeetCode 제출 결과

 

이렇게 구현에 성공하였습니다.

 

3. 시간 복잡도 계산

O(n) = O(n)

 

4. 개선 사항 및 어려웠던 점

주어진 환경 안에선 가장 최적의 방법으로 구현할 것으로 보입니다. 

5. 깃허브

관련 사항은 깃허브에 모두 기재되어 있습니다.