21. Merge Two Sorted Lists

• 해결은 했는데, 공간 복잡도 측면에서 매우 비효율적이었다. 주어진 두 list  의 pointer 들만 잘 바꿔줘도 되는걸, 복잡해서 새로운 node 를 매번 만들었기 때문이다. 
• 아래의 iterative 가 원래 내가 풀고싶던 방식이고, recursive 도 풀기 전 접근 단계에서 생각은 했으나 구현은 못한 방식이다.
• LinkedList  유형의 문제를 풀때는, 
• sentinel node 를 하나 만들어서 return 을 쉽게 하는 것
• node.next.next  식의 접근 방식도 유용하게 쓰이니 기억할 것
• null 체크를 항상 주의 할것

*Iterative

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode ptr1 = l1;
    ListNode ptr2 = l2;
    ListNode sentinel = new ListNode();
    ListNode ptr3 = sentinel;
    while (ptr1 != null && ptr2 != null) {
        if (ptr1.val <= ptr2.val) {
            ptr3.next = ptr1;
            ptr1 = ptr1.next;
        } else {
            ptr3.next = ptr2;
            ptr2 = ptr2.next;
        }
        ptr3.next.next = new ListNode();
        ptr3 = ptr3.next;
    }
    ptr3.next = (ptr1 == null) ? ptr2 : ptr1;
    return sentinel.next;
}

*Recursive

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

*Time complexity

list1 의 node 개수를 N, list2 의 node 개수를 M 이라고 하면, 각 list 를 끝까지 traverse 하므로

O(N+M) 이 되는것으로 보인다.