박종훈 알고리즘 블로그

(Leetcode) 21 - Merge Two Sorted Lists

기회가 되어 달레님의 스터디에 참여하여 시간이 될 때마다 한문제씩 풀어보고 있다.

https://neetcode.io/practice


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)이다. 빅오 표기법상으로는 개선하기 전과 후가 동일하다. 하지만 개선하였다.