[알고리즘] Leetcode_21_Merge_Two_Sorted_Lists

Problem

Solve

public class Leetcode_21_Merge_Two_Sorted_Lists {
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        
        ListNode result = new ListNode();
        ListNode head = result;
        
        
        while(! (list1 == null && list2 == null)){
            int val1 = 101, val2=101;

            if(list1 != null) val1 = list1.val;
            if(list2 != null) val2 = list2.val;
            System.out.println(val1 + " " + val2);

            ListNode temp = new ListNode();

            if(val1 <= val2){
                temp.val = val1;
                list1 = list1.next;  
            }else{
               temp.val = val2;
               list2 = list2.next;                
            }
            result.next = temp;
            result = result.next;    
        }
        
        return head.next;

    }
}

1. iterative 방식
   두 list 의 대소를 비교하면서 최종 반환 노드에 추가시켜줌
   ➡️ result와 head, temp 를 쓰는 것과 return 시 head.next 를 해주는 것 : list1나 list2를 아예 대입을 시켜버리면 뒤의 노드들까지 다 복사가 되는 것이므로 임시적인 노드인 temp를 사용하고 head는 result의 제일 첫 머리 null 을 가리키므로 다음 노드인 head.next 를 반환시킨다.
   ➡️ val1과 val2에 101로 초기화 시켜주는 것 : null 일경우에는 101로 값이 유지되므로써 (이는 문제의 조건에서 val 값은 0부터 100까지이므로 임의의 설정) error 발생 방지

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

    	}
 }

2.recrusive 방식
재귀는 한참 보아도 어렵다.
대소비교를 해서 작은 노드의 next를 다시 재귀적으로 돌린다.
그렇다면 null이 되는 순간들로부터 다시 반환점을 돈다.