Merge Two Sorted Lists

---

💬 문제

[문제 링크]

오름차순으로 정렬된 두 연결 리스트 list1, list2
두 리스트를 합쳐서 정렬된 하나의 리스트로 만들어 헤드 노드를 반환

✍️ 나의 풀이

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function(list1, list2) {
    let head = new ListNode();
    let res = head;
    
    while (list1 && list2) {
        if (list1.val < list2.val) {
            res.next = list1;
            list1 = list1.next;
        } else {
            res.next = list2;
            list2 = list2.next;
        }
        res = res.next;
    }

    res.next = list1 || list2;

    return head.next;
};

반환할 연결 리스트의 첫 노드 head
실제로 이동할 포인터 역할 노드 res
두 리스트 중 하나가 끝날 때까지 돌면서
더 작은 값을 가진 노드를 현재 res에 할당
반복문이 끝나면 남은 리스트를 그대로 res.next에 이어붙임
head의 next 부터 노드를 담았으므로
반환은 head.next를 해야 값이 담긴 첫 노드 반환

📌 결과

Accepted
Runtime 58ms (Beats 77.87%)
Memory 51.11MB (Beats 82.05%)

📚 러닝 포인트

처음에는 res의 각 노드에 값과 next를 따로 넣어줬었는데 매개변수의 노드를 그대로 할당할 수 있다는 생각에 바꿔서 구현할 수 있었다. 그런데 지금은 처음에 빈 노드를 만들고 그 다음 노드부터 값이 들어있도록 구현이 되어 있는데 어떻게 하면 처음부터 할당할 수 있을지 고민하다가 다른 사람들의 코드를 발견했다.

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
}

이렇게 함수 안을 구성해서 재귀 함수로 활용하고 있었다. while문이 대체 되어서 보기에도 깔끔하고 속도도 빠른 것 같았다. 끝에서부터 매개변수를 수정하면서 만들어오는 거라 추가적인 변수도 필요하지 않아서 나름 획기적이라고 생각한 방법이었다. 재귀 함수가 아직 익숙하지 않아서 여기까지 생각하기가 어려웠지만 잘 활용할 수 있도록 해보자...