(Leetcode) 21 - Merge Two Sorted Lists
기회가 되어 달레님의 스터디에 참여하여 시간이 될 때마다 한문제씩 풀어보고 있다.
2주간 미션이 나와서 다시 풀기 시작하였다.
https://leetcode.com/problems/merge-two-sorted-lists/description/
내가 작성한 풀이
두 리스트에서 작은 값을 찾고 작은 값을 새 ListNode에 추가한 뒤 기존의 리스트에서는 지워준다.
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode head = null;
ListNode tail = null;
while(!(list1 == null && list2 == null)) {
ListNode selected;
if (list1 == null) {
selected = list2;
list2 = list2.next;
} else if (list2 == null) {
selected = list1;
list1 = list1.next;
} else if (list1.val < list2.val) {
selected = list1;
list1 = list1.next;
} else {
selected = list2;
list2 = list2.next;
}
ListNode newNode = new ListNode(selected.val);
if(head == null) {
head = newNode;
} else {
tail.next = newNode;
}
tail = newNode;
}
return head;
}
}
TC, SC
시간 복잡도는 O(n)이고, 공간 복잡도는 O(n)이다.
개선해보기
“두 개의 tree의 길이가 차이가 많이 난다면 연산량을 많이 줄일 수 있는 방법이 있을 것 같아요.” 라는 피드백을 받았다. 한쪽이 null 이 된 상태에서도 반복문을 돌기 때문에 이런 피드백을 주신 것 같다.
한쪽이 null 이되면 나머지 쪽은 이어 붙이면 된다.
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode head = new ListNode(0);
ListNode tail = head;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
tail.next = list1;
list1 = list1.next;
} else {
tail.next = list2;
list2 = list2.next;
}
tail = tail.next;
}
if (list1 != null) {
tail.next = list1;
} else {
tail.next = list2;
}
return head.next;
}
TC, SC
시간 복잡도는 O(n)이고, 공간 복잡도는 O(n)이다. 빅오 표기법상으로는 개선하기 전과 후가 동일하다. 하지만 개선하였다.