[LeetCode] 21. Merge Two Sorted Lists

Merge Two Sorted Lists - LeetCode

주어진 Lists 오름차순으로 합친 Node를 반환하는 문제입니다.

 

Example 1:

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

Example 2:

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

Example 3:

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

 

문제 접근

while문 조건으로 두리스트를 null이 아닐때까지 탐색하면서

작은 요소부터 분기문으로 넣어주었습니다.

 

주의할점은 cur = cur.next를 해주어야 다음 노드로 값이 할당된다는 점입니다.

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode listNode = new ListNode(-1);
        ListNode cur = listNode;

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

        if (list1 == null) {
            cur.next = list2;
        } else {
            cur.next = list1;
        }

        return listNode.next;
    }

 

재귀함수를 사용해서 풀어보려고 했지만 풀지 못했습니다...

시간복잡도

list1, list2를 탐색하고 있습니다.

O(n+m)의 시간복잡도가 필요합니다.

 

다른사람의 풀이

재귀함수로 풀이한 로직을 보았습니다.

개인적으로 재귀함수를 잘 사용하고싶은 욕심이 있어 클린하게 작성된 모범답안을 보고 많이 배웠습니다.

 

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null)   return list2;
        if(list2 == null)   return list1;

        if(list1.val < list2.val){
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        }
        else{
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }

 

느낀점

Linked List를 탐색할 수 있어? 라고 물어보는 문제였던거 같습니다.

재귀함수로도 내가 원하는 대로 탐색할 수 있을정도로 연습을 해야겠다고 느꼈습니다.

 

참고

https://leetcode.com/problems/merge-two-sorted-lists/solutions/3939765/recursive-java-solution/