solution

/**
 * 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) {
    if(list1 === null){
        return list2;
    }

    if(list2 === null){
        return list1;
    }

    // 기준으로 사용할 list를 잡고
    // 노드를 하나씩 넘겨가면서 val을 pivot으로 삼는다
    // 그 후, 다른 list의 노드를 순회한다.
    // 기준 list의 현재 노드의 val보다 같거나 크면서, 그 노드의 next의 val보다 작으면
    // 결과로 사용할 list에 추가해나간다.
    let linked_list = new ListNode(0); // 반환용
    let head = linked_list; // 연산용

    // list1과 list2 중 가장 첫 번째 node의 값이 더 작은 애가 기준 노드가 되어야함.
    let base_list;
    let oper_list;
    if(list1.val < list2.val){
        base_list = list1;
        oper_list = list2;
    } else {
        base_list = list2;
        oper_list = list1;
    }

    while(base_list){
        // 기준 노드를 결과 list에 추가
        head.next = new ListNode(base_list.val);
        head = head.next;

        while(base_list.next && oper_list && oper_list.val >= base_list.val && oper_list.val < base_list.next.val){
            head.next = new ListNode(oper_list.val);
            head = head.next;

            oper_list = oper_list.next;
        }

        // 마지막 list1 node에 대한 연산 진행 중이므로
        // 나머지 list2를 전부 head에 연결하면 됨.
        // list1이 마지막 node이면서 list2의 끝까지 연산할 수 있도록 while 조건 설정.
        while(!base_list.next && oper_list){
            head.next = new ListNode(oper_list.val);
            head = head.next;

            oper_list = oper_list.next;
        }

        // 기준 노드를 이동
        base_list = base_list.next;
    }

    return linked_list.next;
};

필자는 기준이 될 리스트와 연산을 진행할 리스트를 구분해서 문제를 해결했다.
우선 기준 리스트를 linked_list에 이어준 뒤,
연산 리스트의 값이 기준 리스트의 값 이상이면서 기준 리스트의 다음 노드 값보다 작으면
linked_list에 이어준다.
그 후, 기준 리스트의 노드를 이동시키고 다시 연산을 반복한다.
만약 기준 리스트의 next가 null이라면 끝까지 닿은 것이므로,
연산 리스트의 나머지 부분을 전부 linked_list에 이어준다.

Linked List가 앞에서부터 탐색을 해야하다보니 이 방법이 옳다고 생각했으나
시간 복잡도, 메모리 성능이 모두 최악의 수준으로 나왔다.

다른 분의 solution

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    if (!l1) return l2;
    if (!l2) return l1;
    if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
};

필자가 고생해서 만든 코드를 재귀를 활용하여 구현하신 분이 계셨다.
논리는 완전히 동일하다.
기준이 되는 리스트의 값보다 크거나 같으면서 그 다음 node보다 작으면 계속해서 이어나가고,
아니라면 다른 리스트를 이어주는 방식이다.

알고보니 Merge sort는 Divide and Conquer를 기본 개념으로 사용하고 있으며,
이를 해결하는데 가장 적합한 방법이 Recursion이었던 것이다.