[Easy] LeetCode - no.21 Merge Two Sorted Lists : Java

https://leetcode.com/problems/merge-two-sorted-lists/description/?envType=study-plan-v2&envId=top-interview-150\

 

 

문제

두 개의 정렬된 연결 리스트가 주어졌을 때, 이를 정렬된 순서(오름차순) 를 지키며 병합시킬 것

 

Example 1

 

 

 

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

 

 

 

 

 

풀이1

    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                list1.next = mergeTwoLists(list1.next, list2);
                return list1;
            } else {
                list2.next = mergeTwoLists(list1, list2.next);
                return list2;
            }
        }

        if (list1 == null) {
            return list2;
        }

        return list1;
    }

 

참고

https://leetcode.com/problems/merge-two-sorted-lists/solutions/3177193/simple-java-runtime-1-ms-beats-100/?envType=study-plan-v2&envId=top-interview-150

 

• 재귀 사용
• list1과 list2가 모두 null이 아닐 경우
  • list1.val과 list2.val을 비교하여 더 작은 쪽을 계산
    • list1.next = mergeTwoLists(list1.next, list2) or list2.next = mergeTwoLists(list1, list2.next)
    • return list1 or list2
• list1이 null이라면 list2 반환, 아니라면 list1 반환
• 시간복잡도 : O(N)

💬 좋은 방법이지만 한 번에 와닿지 않음

 

 

풀이2

    public static ListNode mergeTwoLists2(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0);
        ListNode runner = dummy;

        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                runner.next = list1;
                list1 = list1.next;
            } else {
                runner.next = list2;
                list2 = list2.next;
            }

            runner = runner.next;
        }

        if (list1 != null) {
            runner.next = list1;
        }

        if (list2 != null) {
            runner.next = list2;
        }

        return dummy.next;
    }

 

참고

 

• dummy 라는 ListNode를 미리 선언 (계산 결과를 저장할 연결 리스트)
• dummy.next를 반환해야 하기 때문에 계산에 사용할 runner를 따로 선언
• list1.val과 list2.val을 비교하며 runner 계산
• dummy.next 반환 (맨 첫번째 값은 필요하지 않기 때문)
• 시간복잡도 : O(N + M) (N = list1의 길이, M = list2의 길이)

💬 훨씬 직관적이고 이해하기 쉬운 코드