[LeetCode][Grind 75] 21. Merge Two Sorted Lists

문제 해결 방안

1. 첫번째 시작 노드를 생성한다
2. 각각의 노드 리스트 중 하나라도 끝에 도달할 때까지 반복하면서 더 작은 값을 새로운 시작 노드에 이어 붙인다.
3. 하나가 끝에 도달해서 반복문이 끝나면, 나머지 노드 리스트 전체를 새로운 노드 끝에 이어붙인다.

---

겪은 문제점

1. 마지막에 새로운 노드의 헤더를 리턴해야하는데, 헤더를 어떻게 가져올건가

답을 알고보면 쉬운 문제이지만, 계속 next로 가서 노드를 이어붙여야하는데, 헤더를 어떻게 가져올지 아이디어가 떠오르지 않았습니다.

헤더를 가리키는 변수를 하나 더 생성해서 해결할 수 있었습니다.

ListNode start = new ListNode();
ListNode tmp = start;

---

정답 코드

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode start = new ListNode();
    ListNode tmp = start;

    while(list1 != null && list2 != null){
        if(list1.val < list2.val){
            tmp.next = new ListNode(list1.val);
            list1 = list1.next;
        }else{
            tmp.next = new ListNode(list2.val);
            list2 = list2.next;
        }
        tmp = tmp.next;
    }

    tmp.next = list1==null?list2:list1;

    return start.next;
}