21. Merge Two Sorted Lists

주어진 두 개의 정렬된 연결 리스트를 하나의 정렬된 리스트로 병합하는 문제입니다. 첫 번째 두 리스트의 노드를 이어 붙여서 새로운 정렬된 연결 리스트를 만들어야 합니다. 병합된 연결 리스트의 헤드 노드를 반환해야 합니다.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    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;
        }
    }
}

기본 케이스:
만약 list1이 null이면 list2를 반환합니다.
만약 list2가 null이면 list1을 반환합니다.

재귀적 케이스:
list1의 현재 노드의 값과 list2의 현재 노드의 값을 비교합니다.
만약 list1의 현재 노드의 값이 list2의 현재 노드의 값보다 작거나 같다면, list1.next와 list2를 병합하고, list1의 현재 노드의 next 참조를 병합된 리스트의 헤드로 업데이트합니다.
그렇지 않은 경우, list1과 list2.next를 병합하고, list2의 현재 노드의 next 참조를 병합된 리스트의 헤드로 업데이트합니다.
이 코드는 두 정렬된 연결 리스트를 재귀적으로 병합하여 새로운 정렬된 연결 리스트를 생성하는 방법을 보여줍니다.