[Linked List] Sort List

Linked List를 오름차순으로 정렬하라는 문제이다.

공간복잡도가 O(1)이라 최대한 해당 리스트내에서 sort해보겠다

 

일단 경계값을 제외한다

 

이후 메인로직에 서는 Merge Sort를 이용한다

분할-> 합병의 순서로 배열을 처리한다.

 

분할의 경우 반으로 쪼갠다. 보통 Array를 정렬하는 경우 반으로 나누면 되는데, Linked List는 길이를 알 수 없으므로

fast와 slow라는 노드를 두고, slow는 한칸, fast는 두칸씩 움직이면 fast가 끝나는 시점에서 딱 반절의 위치를 알수 있게 된다. 

이를 재귀로 길이가 0또는 1이 될때까지 쪼갠다.

이때 prev는 이전 함수에서 사용한 인덱스이므로 next를 null로 설정해주어야 한다.

 

 

분할이 끝나면 합병을 진행한다

재귀를 통해 0또는 1길이의 부분배열까지 쪼개진 후 합병이 진행된다.

합병은 오름차순이므로 조건대로 value가 더 작은 노드를 배치한다.

이때 간이노드인 newHead를 이용한다.

이 과정에서 p1과 p2가 2개이상의 원소를 가진 배열인 경우 비교가 복잡하다.

이러한 경우에는 각 head들 끼리 순차적으로 비교하면 된다.

상기 예시에서도 p2.val>p1.val이므로 p1을 먼저 now의 next노드로 만들고, p1.next로 p1을 옮겨준다

이렇게 연쇄적으로 비교하면 하나의 배열이 리턴된다.

 

최종적인 답은 다음과 같다.