leetcode 21. Merge Two Sorted Lists

 

 

정렬되어있는 상태의 2개의 ListNode  이것을 비교하고 가장 작은 수가 무엇인지 확인 후

return 할 list에 add 해가는게 좋아보인다.

 

책에서는 재귀함수를 추천했다.

 

list1 과 list2의 현재값을 비교한다음, 더 작은쪽의 next 값을 재세팅 하는 방식이다.

 

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //두개의 list 값중에 낮은 숫자를 알아내야하고 null인 경우도 고려해야된다.

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

 

만약 list 1 = [1,2] & list2 = [1,3] 이렇게 있다고 해보자.

 

 

1.

else 로 들어가서 list2.next = mergeTwoLists([1->2], 3)

이렇게 보낼것이다..

 

2.

첫번째 if로 들어가서 list1.next = mergeTwoLists(2, 3)

 

3. 

첫번째 if로 들어가서 list1.next = mergeTwoLists(null, 3)

이제 list1.next 는 없으니까  위에 걸러주는 것을 만들어주자.

 

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

        if (list1.val < list2.val) {
        	//list2가 더 클 경우
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
        	//list1이 더 클 경우
        	list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

 

4.

if null에 걸려서 list2 return.

 

5.

3번에서 실행됐던 함수로 돌아옴.

list2의 값인 3 이 return 되고 그것이 list1.next = 3

이때 list1은 2 이기때문에 list.next 로 받은 3을 합치면 return 값은 2->3

 

6. 2번에서 실행됐던 함수로 돌아옴

list1.next = 2->3

기존 list1와 next를 합치면 1->2->3

 

7. 1번에서 실행했던 함수로 돌아옴

기존 list2와 next를 합치면 1->-1->2->3

 

 

이런식으로 비교했을 때 낮은 숫자쪽에 next를 설정하는 방식으로 풀이했다.