[LeetCode] 21. Merge Two Sorted Lists #Easy #Java

문제
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.

예제 1

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

예제 2

Input: list1 = [], list2 = []
Output: []

예제 3

Input: list1 = [], list2 = [0]
Output: [0]

제약조건

✅ The number of nodes in both lists is in the range [0, 50].

✅ -100 <= Node.val <= 100

✅ Both list1 and list2 are sorted in non-decreasing order.

 

문제풀이

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 1. 변수 선언 및 초기화
        ListNode resultNode = new ListNode();
        ListNode tempNode = resultNode;

        // 2. 리스트에 결과 순서대로 추가
        while (list1 != null || list2 != null) {
            if (list1 == null) {
                tempNode.next = list2;
                list2 = list2.next;
            } else if (list2 == null) {
                tempNode.next = list1;
                list1 = list1.next;
            } else {
                if (list1.val <= list2.val) {
                    tempNode.next = list1;
                    list1 = list1.next;
                } else {
                    tempNode.next = list2;
                    list2 = list2.next;
                }
            }
            tempNode = tempNode.next;    
        }    

        // 3. 반환
        return resultNode.next;
    }
}

• LinkedList와 참조 개념을 알고 있다면 쉽게 풀 수 있는 문제다.
• 주어진 파라미터가 문제에서 주어진 ListNode 인스턴스가 아닌 배열이나 리스트였다면 덱을 사용할 수 있었을 것 같다.
• 참고로 ListNode는 문제에서 주어지는 클래스로, 주석을 통해 어떻게 작성되어 있는지 알 수 있다.

 

도식화

• 로컬 변수는 스택 메모리에, 인스턴스는 힙 메모리에 생성된다.

 

• while문을 순회하며 list1과 list2의 값을 비교한다.
• tempNode의 next 필드에 더 작은 값에 해당하는 ListNode를 대입한 후에, next 필드에 해당하는 ListNode를 참조한다.

 

• while문이 종료되면 위 이미지와 같은데, resultNode의 next 필드를 통해 예상한 결과물을 반환할 수 있다.
• 참고로 list1과 list2가 메서드 실행 중간에 null을 참조하더라도 바로 사라지지 않고, 메서드가 종료되면 메모리 상에서 없어진다고 한다.

 

마치며

PPT로 정리하는데 2시간 걸렸다. ㅋㅋㅋ
개발 블로그 이웃님이 코딩테스트 포스팅에 로직을 그림으로 정리하시는 걸 보고 따라 해봤는데 쉽지 않다. 😂  

최근 일하면서 다른 사람이 이해하기 쉽게 산출물을 만드는 것도 개발자의 능력임을 알게 되었는데,
가끔 정리할 만한 개념이 나온다면 시간이 좀 들더라도 평소에 연습해야겠다.
누군가가 처음 봤을 때도 이해하기 쉽게끔 산출물을 잘 만드시는 분들은 정말 대단한 것 같다.

 

이미지 출처

[김은우의 에듀테크 트렌드 따라잡기] 코딩 교육 사이트 LeetCode가 보여주는 코딩교육의 핵심