(Leetcode) 143 - Reorder List
기회가 되어 달레님의 스터디에 참여하여 시간이 될 때마다 한문제씩 풀어보고 있다.
https://leetcode.com/problems/reorder-list/
내가 작성한 풀이
두 가지 방법으로 풀어봤다.
list 로 풀기
class Solution {
public boolean isValidBST(TreeNode root) {
return dfs(root.left, (long) Integer.MIN_VALUE - 1, root.val)
&& dfs(root.right, root.val, (long) Integer.MAX_VALUE + 1);
}
private boolean dfs(TreeNode node, long min, long max) {
if (node == null) {
return true;
}
// left로 갈 때 max를 자신으로, right로 갈 때는 min을 자신으로
if (!(dfs(node.left, min, node.val)
&& dfs(node.right, node.val, max))) {
return false;
}
return node.val > min && node.val < max;
}
}
TC, SC
시간 복잡도는 O(n)이고, 공간 복잡도는 O(n)이다.
pointer 로 풀기
포인터로도 풀 수 있을 것 같아서 찾아보았더니 방법이 있는것 같길래 참고하여 코드를 작성해보았다. slow와 fast를 이용하여 뒤집을 부분과 유지할 부분을 나누는 것이 재밌는 접근이였던것 같다.
class Solution {
public void reorderList(ListNode head) {
ListNode prev = null;
ListNode slow = head;
ListNode fast = head;
while(slow != null && fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
if (prev == null) {
return;
}
prev.next = null;
ListNode current = head;
ListNode reversed = reverse(slow);
while(true) {
ListNode temp = current.next;
if (reversed != null) {
current.next = reversed;
reversed = reversed.next;
current = current.next;
}
if (temp != null) {
current.next = temp;
current = current.next;
} else {
current.next = reversed;
break;
}
}
}
public ListNode reverse(ListNode treeNode) {
ListNode current = treeNode;
ListNode prev = null;
while(current != null) {
ListNode temp = current.next;
current.next = prev;
prev = current;
current = temp;
}
return prev;
}
}
TC, SC
시간 복잡도는 O(n)이고, 공간 복잡도는 O(1)이다.
마무리
두번째 풀이가 공간 복잡도가 줄었으나 다만 실제로 수행된 결과를 비교해보면 시간과 공간 측면에서 큰 차이는 없었다. 오히려 늘어난 면이 있다. 코드도 많이 복잡해졌다고 생각한다.
| 방식 | 실행 시간 | 메모리 |
|---|---|---|
| list | 3 ms | 47.6 MB |
| pointer | 2 ms | 48.2 MB |
물론 input 케이스에 따라 달라질 수 있을 것이다.
일단은 어떻게 접근할지 여러가지 방법으로 고민하는 것에 의의를 둬야 할 것 같다.