문제 먼저 읽기
- linkedlist의 head인 ListNode가 하나 주어집니다.
- 이 리스트를 오름차순으로 정렬하고 head를 반환합니다.
- 시간복잡도 O(nlogN), 공간복잡도 O(1)의 답변이 있는 모양입니다 🫠
- Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?
어떻게 풀까?
생각
- 처음 문제를 읽고 좀 당황했습니다. linked list를 정렬을 다시 해본적이 없었기 때문입니다.
- 가장 먼저 든 생각은 새로운 LinkedList를 만들어서 이전 리스트를 탐색함과 동시에 새로운 리스트에 값을 넣어주는 것입니다. 이 경우 시간복잡도는 O(n^2)이 될 것으로 예상됩니다. 새로운 리스트에 값을 넣을 때 매번 처음부터 다시 탐색해야 하기 때문입니다.
- 두번째 생각한 것은 LinkedList의 중간 노드를 찾고 병합 정렬을 해보는 것입니다. 이 경우 시간복잡도는 O(nlogN) 으로 좀 더 개선할 수 있어보입니다.
- 여기서 LinkedList의 중간노드를 찾는 로직을 처음으로 시도해보아야 했는데요.
수도코드
class Solution {
public ListNode sortList(ListNode head) {
// 더 분할할 수 없으면 멈추는 코드
ListNode mid = null; // 중간 지점을 찾는다.
ListNode slow = head;
ListNode fast = head; // 같은 시작지점
while (fast != null) {
mid = slow; // 연결을 끊을지점
slow = slow.next;
fast = fast.next.next; // 2씩 증가
}
mid.next = null; // 연결 끊기
ListNode head1 = sortList(head); // 분할하여 정렬
ListNode head2 = sortList(slow);
return merge(head1, head2);
}
private ListNode merge(ListNode node1, ListNode node2) {
ListNode temp = new ListNode(Intenger.MIN_VALUE);
ListNode cur = temp;
while (node1 != null && node2 != null) { // 둘 중 하나가 끝날 때까지
if (node1.val < node2.val) {
cur.next = node1;
node1 = node1.next; // 다음 노트로 커서 옮기기
} else {
cur.next = node2;
node2 = node2.next;
}
cur = cur.next;
}
// 남은 노드랑 연결해주는 코드
return temp.next;
}
}
결과
java.lang.NullPointerException: Cannot read field "next" because "<local4>.next" is null
at line 26, Solution.sortList
at line 54, __DriverSolution__.__helper__
at line 84, __Driver__.main
- 테스트는 통과했는데 null point exception이 제출 중에 발생하였습니다.
- fast = fast.next.next; 와 if (head.next==null)코드가 발생 원인이었습니다. 조건문에 추가로 null exception 방지를 위한ㄴ 조건을 써주었습니다.
class Solution {
public ListNode sortList(ListNode head) {
// 더 분할할 수 없으면 멈추는 코드
if (head==null || head.next==null) { // 체크 순서에 유의하여야 합니다.
return head;
}
// 중간 지점을 찾는다.
ListNode mid = null;
ListNode slow = head;
ListNode fast = head; // 같은 시작지점
while (fast != null && fast.next != null) { // fast가 null이 아니어도 fast.next가 null 이면 fast.next.next가 불가능합니다.
mid = slow; // 연결을 끊을지점
slow = slow.next;
fast = fast.next.next; // 2씩 증가
}
mid.next = null; // 연결 끊기
// 분할하여 정렬
ListNode head1 = sortList(head);
ListNode head2 = sortList(slow);
return merge(head1, head2);
}
<aside> 💡 Success
Runtime: 9 ms, faster than 91.35% of Java online submissions for Sort List.
Memory Usage: 56.3 MB, less than 22.30% of Java online submissions for Sort List.
</aside>
다른 풀이 방식과 문제 회고
- 시간복잡도가 8ms 인 풀이
- int[] 에 값을 저장하고 sort하여 푼 방법입니다.
class Solution {
public ListNode sortList(ListNode head) {
int count = 0;
ListNode temp = head;
while(temp!=null){
count++;
temp = temp.next;
}
int[] arr = new int[count];
temp = head;
count = 0;
while(temp!=null){
arr[count++] = temp.val;
temp = temp.next;
}
Arrays.sort(arr);
temp = head;
count = 0;
while(temp!=null){
temp.val = arr[count++];
temp = temp.next;
}
return head;
}
}
- 시간복잡도가 2ms 인 풀이
- 분할정복의 다른 예시입니다. 이미 정렬된 head는 건너뛰고 분할해준 것으로 보입니다.
class Solution {
public ListNode sortList(ListNode head) {
return sortList(head, null);
}
ListNode sortList(ListNode p, ListNode q) {
if (p == null || p == q) {
return p;
}
boolean sorted = true;
ListNode curr = p;
while (curr.next != null && curr != q) {
if (curr.val > curr.next.val) {
sorted = false;
break;
}
curr = curr.next;
}
if (sorted) {
return p;
}
ListNode pre = p;
ListNode head = p;
curr = pre.next;
while (curr != null && curr != q) {
ListNode next = curr.next;
if (curr.val < p.val) {
pre.next = next;
curr.next = head;
head = curr;
} else {
pre = curr;
}
curr = next;
}
p.next = sortList(p.next, q);
return sortList(head, p);
}
}
