파이문

문제 설명 링크드 리스트가 주어지는데, 상수의 공간 복잡도와 O(nlogn) 의 시간 복잡도로 정렬하는 문제다. 코드는 여기서 확인 가능하다. 솔루션 꼼수 가장 쉬운 방법은 링크드 리스트를 배열로 만들어서 언어에 built-in 된 sort 함수를 사용하는 것이다. 참고로 python 은 timsort 라는 알고리즘으로 sort 가 구현되어 있다. 아니면 sort 함수 말고 직접 정렬을 구현하면 될 것 같다. 하지만 이러면 constant space complexity 를 만족할 수가 없다. 두뇌 풀가동 merge sort 로 하면 될 것 같았다. 이때 절반을 divide 해야 하는데 배열이랑 다르게 사이즈를 알 수가 없다. 이를 위해 fast-slow 로 노드를 순회한다. 이는 tortoise-hare..