• Sort List
  • 문제
  • 조건
  • 예제
  • 해결
    • 1st
      • 1 생각

Sort List

문제

Given the head of a linked list, return the list after sorting it in ascending order.
Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

• 연결리스트가 주어졌을 떄, 오름차순으로 정렬
• O(n logn) 시간 복잡도와 O(1) 공간 복잡도

조건

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

예제

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

Input: head = []
Output: []

해결

1st

1 생각

• 시간복잡도 O(n logn)이려면 병합정렬 또는 퀵 정렬 정도 되어야 한다
• 공간복잡도 O(1)까지 고려하면 테이블 상 힙 정렬 또는 스무스 정렬
• 일단 퀵 정렬로 해보자.