[LeetCode] 148. Sort List

😎풀이

해당 풀이는 병합 정렬을 활용한 풀이이다.

풀이 절차는 다음과 같다.

1. 입력받은 연결 노드의 중간 노드를 기준으로 분리(slow, fast)
2. 재귀적으로 분리된 연결 노드를 분리
3. merge 함수를 통해 전달된 두 노드를 정렬하며 병합

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function sortList(head: ListNode | null): ListNode | null {
    if(!head || !head.next) return head

    let slow = head
    let fast = head
    let prev = head
    
    // 중간 노드 탐색
    while(fast && fast.next) {
        prev = slow
        slow = slow.next
        fast = fast.next.next
    }

    // 리스트 분리
    prev.next = null

    // 좌 우 연결노드 재귀적 분할
    const left = sortList(head)
    const right = sortList(slow)

    // 분할 노드 정렬 및 연결
    return merge(left, right)
};

function merge(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    const dummy = new ListNode()
    let l3 = dummy
    
    // l1과 l2 정렬
    while(l1 && l2) {
        if(l1.val < l2.val) {
            l3.next = l1
            l1 = l1.next
        } else {
            l3.next = l2
            l2 = l2.next
        }
        l3 = l3.next
    }

    // 잔여 연결노드 연결
    if(l1) l3.next = l1
    if(l2) l3.next = l2

    return dummy.next
}