[LeetCode] Sort List - Javascript

Sort List

[주어진 연결리스트 정렬 하기]

 

제약 조건 

The number of nodes in the list is in the range [0, 5 * 10^4].
-10^5 <= Node.val <= 10^5

 

Example

문제 접근 방식

연결 리스트로 되어 있는 노드들을 정렬을 해서 리턴을 해야 한다.
문제 밑에 Follow up으로 시간 복잡도를 O(n logn)으로 풀 수 있냐고 물어보는 거 보니,

해당 문제는 O(n logn) 즉 병합 정렬로 푸는 게 문제의 의도인 거 같다.

 

하지만 해당 문제를 병합 정렬로 풀기 위해선 주어진 연결 리스트의 길이를 알아야 하는데, 길이를 어떻게 알 수 있을까에 대한 의문을 풀어내지 못해 배열을 통해 정렬 하는 방법으로 풀이했다.

먼저 head가 가리키는 주소를 arr의 빈 배열에 넣는다.
그 후 head = head.next를 통해 head가 undefined가 될 때까지 배열에 주소를 넣은 후
해당 배열을 오름차순으로 sort 한다.

 

배열의 길이만큼 반복문을 순회하며, arr[i].next에 arr[i+1]의 정렬된 값을 넣고 해당 데이터가 없다면,

에러가 나지 않게 null을 삽입해 준다.

 

이렇게 하는 이유는, 아래와 같은 연결 리스트가 있다고 할 때 현재 head는 4를 가르키는게 아닌, [4,2,1,3] 자체를 가르키고 있고, head.next는 [2,1,3]을 가르키고 있기때문이다. 

arr 배열의 정렬되기 전과 정렬되기 후이다.

[ [4,2,1,3], [2,1,3], [1,3], [3] ] => [ [1,2,3,4], [2,3,4], [3,4], [4] ]

현재 arr[0] 배열이 정렬이 모두 되어 있기에 해당 배열(주소)를 리턴한다.

 

전체코드

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function(head) {
  let arr = [];
  while (head) {
    arr.push(head);
    head = head.next;
  }
  arr = arr.sort((a, b) => a.val - b.val);
  for (let i = 0; i < arr.length; i++) {
    arr[i].next = arr[i + 1] || null;
  }
  return arr[0] ?? null;
};