[LeetCode] 21. Merge Two Sorted Lists

leetcode.com/problems/merge-two-sorted-lists/

 

솔직히 말하자면, 클래스 활용문제를 보면 (특히 Node 문제) 잠깐 머뭇거리게 된다.

그렇지만 저번에 이진트리 때 비슷한 문제를 풀었던 기억이 있으니까, 우선 주어진 class를 파악해보려고 노력했다.

역시 익숙해지는 게 중요하다고 느꼈다. 한번 해보니까 감이 잡히는 듯

널 체크 부분을 놓쳐서 수정하느라 30분은 넘었지만 뿌듯하다 ✨

 

주어진 ListNode 클래스 정의

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

생성자 부분을 주목해야한다. ListNode(int val, ListNode, next)를 활용해야겠다는 생각이 번뜩 들었다.

 

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode sort = new ListNode();

        if(l1==null && l2==null) {
            return null;
        }else{
            if (l1==null){
                return l2;
            }else if(l2==null){
                return l1;
            }else{
                // if l1 has next or l2 has next
                // compare each val
                // save sorted result into sort ListNode
                if(l1.val<l2.val){
                    sort.val = l1.val;
                    sort.next = mergeTwoLists(l1.next, l2);
                }else{
                    sort.val = l2.val;
                    sort.next = mergeTwoLists(l1, l2.next);
                }
            }
        }
        return sort;
    }

 

풀이

1. 주어진 매개변수가 모두 null일경우 null return
2. 노드는 이미 오름차순 정렬된 것이므로 둘 중 하나가 null 일경우, null이 아닌 노드를 return
3. 둘 다 null이 아니라면 
   1. 노드에 담긴 값을 체크한다.
   2. 작은 값을 멤버변수 val 에 먼저 담는다.
   3. 비교할 다음값을 재귀함수를 사용해서 다시 반복 비교하며 담기

---

구조를 이해하고 익숙해지는 게 답인 거 같다. 앞으로도 꾸준히 하자 화이팅 !!!!

+) 이진트리 문제를 풀었던 경험이 많이 도움이 됐다.

 

Binary Tree Inorder Traversal

[LeetCode] Binary Tree Inorder Traversal