지금 바로 떠나자 먹으러....

문제:

정렬된 두 링크드 리스트를 합쳐서 하나의 정렬된 링크드 리스트로 반환해라.

예제:

입력: 1->3->4, 1->5->6

출력: 1->1->3->4->5->6

링크드 리스트 클래스 구조는 다음과 같다.

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

구현되어야 할 함수의 선언은 다음과 같다.

ListNode mergeTwoLists(ListNode l1, ListNode l2);

풀이:

재귀함수를 이용하면 간단히 풀 수 있는 문제이다.

첫 번째 노드의 값을 비교해서 더 큰 값이 작은 값의 next가 되면 된다.

그리고 작은 값의 next와 큰 값과 다시 비교해서 merge하는 과정을 계속 반복하여 null이 나올 때 까지 한다면

두 링크트 리스트가 정렬된 상태로 합쳐지게 된다.

1. 입력된 두 노드의 값을 비교한다.

2. 작은 값의 next와 큰 값을 인자로 다시 merge함수를 다시 호출한다.

3. merge함수에서 나온 결과를 작은 값의 next로 한다.

Java code:

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        ListNode result;
        
        if(l1.val <= l2.val) {
            result = l1;
            l1.next = mergeTwoLists(l1.next, l2);
        }
        else {
            result = l2;
            l2.next = mergeTwoLists(l1, l2.next);;
            
        }
        
        return result;
    }
}