요즘 leetcode like top 100을 풀고 있는데 속도를 반드시 개선하고 싶은 문제를 발견했다.
Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.
Example:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
맨 처음 생각한 풀이는
1.
ListNode 를 순회 하면서 값을 List 에 add 하고
2.
sorting 을 실행 한 뒤에
3.
그 값을을 다시 순회하면서 ListNode 를 만들어 반환하면 되겠다
라고 생각했다.
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null && l2 == null) return null;
List<Integer> nums = new ArrayList<>();
while (Objects.nonNull(l1)) {
nums.add(l1.val);
l1 = l1.next;
}
while (Objects.nonNull(l2)) {
nums.add(l2.val);
l2 = l2.next;
}
Collections.sort(nums);
ListNode result = new ListNode(nums.get(0));
ListNode node = result;
for (int i = 1; i < nums.size(); i++) {
node.next = new ListNode(nums.get(i));
node = node.next;
}
return result;
}
}
Java
복사
이건 좀 자존심 상하는데.. 내가 하위 20%라니…
아 물론.. List 를 만들어서 value 를 저장하고 sorting 을 하고 이게 효율적인 알고리즘은 아닐 것이다. ㅠㅠ
분명히 누군가는 while 한번만 쓰고 끝냈을텐데
그래서 다음과 같은 기준을 정했다.
1.
while 은 딱 한번만 돌자
2.
sorting 은 내가 직접 한다.
두개를 비교해서 값을 할당하면 자연스럽게 sorting 이 되겠지?
while 을 딱 한번만 돌게 하려면 어떻게 해야할까?
l1, l2 가 둘 중 하나라도 null 상태가 아니라면, 계속 while 이 돌도록 해야겠다. (아 그럼 2n2n 이 되는건가..?) 나중에 생각해야지
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null && l2 == null) return null;
ListNode result = new ListNode(-100);
ListNode node = result;
while (l1 != null || l2 != null) {
if ( l1 == null ) {
node.next = new ListNode(l2.val);
l2 = l2.next;
} else if (l2 == null){
node.next = new ListNode(l1.val);
l1 = l1.next;
} else if (l1.val >= l2.val) {
node.next = new ListNode(l2.val);
l2 = l2.next;
} else if (l1.val < l2.val) {
node.next = new ListNode(l1.val);
l1 = l1.next;
}
node = node.next;
}
return result.next;
}
}
Java
복사
아 코드가 너무 지저분한데… 똑같은 동작을 하는 코드를 if 문 안에서 or 로 묶는다면, 앞에 statement 늘 잘 돌고, 다음 값을 비교하는 condition 에서 NPE 가 발생한다.
[1,2,3]
[4,5,6]
Java
복사
이걸 더 줄여서 l1 을 result 에 넣었을 때, l2 값을 넣을까 했는데 그것도 말이 안된다. 위의 case 처럼 l1 이 먼저 모두 result 에 들어가고 l2 의 값들이 result 로 들어가는 케이스라면?
결국 이 방법이 가장 괜찮은것 같다
