leetcode - sort list / javascript

leetcode의 sortlist 를 풀었다.

 

연결리스트를 정렬하는 문제이다.

n log n으로 정렬해야 한다.

 

병합정렬이나 퀵 정렬이 n log n의 시간 복잡도를 가진다. 일반적인 프로그래밍 언어의 내장 sort 함수는 n log n의 복잡도를 가진다.

 

문제에서 n log n이 나오면 병합정렬, 퀵정렬을 떠올려야 한다.

 

아래 코드는 나의 답안이다.

 

처음에는 javascript 로 풀다가. 제출 후에 타입 에러가 자꾸 났다.

그래서 타입스크립트로 바꿨다. 로컬에서는 deno 를 써서 실행했다.

 

function pushList(head: ListNode, arr: number[]): any {
  if (!head.next) {
    arr.push(head.val);
    return;
  } else {
    arr.push(head.val);
    return pushList(head.next, arr);
  }
}

// 연결리스트의 마지막 노드 찾기
function findLastNode(head: ListNode | null): any {
  if (!head || !head.next) {
    return head;
  } else {
    return findLastNode(head.next);
  }
}

function solution(head: ListNode | null): ListNode | null {
  if (!head || !head.next) {
    return head;
  }
  const temp: number[] = [];
  pushList(head, temp); // 리스트 세팅 끝
  // //정렬
  temp.sort((a, b) => a - b); // 오름차순 정렬
  // // list 에 하나씩 다시 push
  const firstNode = new ListNode(temp[0]);
  for (let i = 1; i < temp.length; i++) {
    const last: any = findLastNode(firstNode);
    last.next = { val: temp[i], next: null }

  }
  return firstNode;
};

 

먼저 리스트가 비어있거나 1개라면 그대로 리턴한다.

 if (!head || !head.next) {
    return head;
 }

 

먼저 연결리스트를 모두 탐색해서 배열로 만든다.

함수를 하나 작성했다.

function pushList(head: ListNode, arr: number[]): any {
  if (!head.next) {
    arr.push(head.val);
    return;
  } else {
    arr.push(head.val);
    return pushList(head.next, arr);
  }
}

노드(head)를 하나 받는다.

노드(head)의 next 가 null이면 head.val을 배열에 넣는다.

null이 아니라면 val을 배열에 담고 다음 노드(head.next)에 대해서 함수를 또 호출한다.

 

예시를 통해서 살펴보자.

5 -> 3- > 1 이런 숫자가 있다면.

 

5 의 값을 배열에 담는다. [ 5 ]

함수를 재귀적으로 호출한다.

pushList( 3 , [5]) 

 

3을 배열에 담는다. [5 , 3]

그리고 함수를 재귀적으로 호출한다.

 

pushList(1 , [5, 3])

1을 배열에 담는다. [5, 3, 1]

head.next 가 이제 없다.

그러면 함수를 더 호출하지 않는다.

arr 에 [5, 3, 1] 이 담겼다.

 

이제 sort 함수를 써서 정렬한다.

temp.sort((a, b) => a - b); // 오름차순 정렬

 

이제 다시 연결리스트를 만든다.

 const firstNode = new ListNode(temp[0]);
  for (let i = 1; i < temp.length; i++) {
    const last: any = findLastNode(firstNode);
    last.next = { val: temp[i], next: null }
  }

배열을 돌면서 노드의 마지막에 추가한다.

노드의 마지막에 다음 노드를 추가해야한다.

 

그래서 findLastNode라는 함수를 만들었다.

// 연결리스트의 마지막 노드 찾기
function findLastNode(head: ListNode | null): any {
  if (!head || !head.next) {
    return head;
  } else {
    return findLastNode(head.next);
  }
}

head.next가 없으면 head를 리턴한다.

head.next가 있다면 다음 노드를 탐색한다.  findLastNode(head.next)

 

이렇게 추가하고 결과를 리턴한다.

풀고 나니 부족한 점이 많은 풀이였다.