[LeetCode] 23. Merge k Sorted Lists

ListNode를 병합하는 문제이다.

모든 노드를 한번에 병합하려 생각하면 어려우니

두 노드씩 묶어 병합하여 해결이 가능하다.

😎풀이

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
    // 빈 입력 처리
    if (lists.length === 0) return null;
    
    // 병합 함수 정의
    const merge = (l1: ListNode | null, l2: ListNode | null): ListNode | null => {
        // 더미 노드 생성
        const dummy = new ListNode(0);
        let current = dummy;
        
        // 두 리스트를 비교하며 병합
        while (l1 !== null && l2 !== null) {
            if (l1.val < l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }
        
        // 남은 노드 처리
        if (l1 !== null) current.next = l1;
        if (l2 !== null) current.next = l2;
        
        return dummy.next;
    }
    
    // 분할 정복 방식으로 리스트 병합
    while (lists.length > 1) {
        const mergedLists = [];
        
        // 두 개씩 리스트를 병합
        for (let i = 0; i < lists.length; i += 2) {
            const l1 = lists[i];
            const l2 = (i + 1 < lists.length) ? lists[i + 1] : null;
            mergedLists.push(merge(l1, l2));
        }
        
        // 병합된 리스트로 업데이트
        lists = mergedLists;
    }
    
    // 최종 병합된 리스트 반환
    return lists[0];
}