[java] 21. Merge Two Lists

※Recursion

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = 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){
            list1.next = mergeTwoLists(list1.next, list2); 
            return list1; 
        } else{
            list2.next = mergeTwoLists(list1, list2.next); 
            return list2; 
        }
    }
}

 

1. list1이나 list2가 NULL 일 경우, 나머지 연결리스트 반환

2. 둘다 NULL일 경우, NULL 리턴 

3. next 노드 통해서 다음 노드 탐색 가능. 

 

4. list1의 첫 노드가 list2보다 작다면 list1.next는 mergeTwoLists(list1.next, list2) 반환 

반대로 list2의 첫 노드가 list1보다 작다면, list2.next는 mergeTwoList(list1, list2.next) 반환