[LeetCode] 143. Reorder List

😎풀이

해당 문제는 다음과 같은 절차로 풀이해야 한다.

1. slow와 fast 포인터를 두어 각각 다르게 전진하며 중간 지점을 탐색한다.
2. 이후 두 번째 절반 노드 목록을 뒤집는다(reverse)
3. 두 노드 목록을 연결한다.

function reorderList(head: ListNode | null): void {
    if (!head || !head.next) return;

    // 리스트의 중간 지점 찾기
    let slow: ListNode | null = head;
    let fast: ListNode | null = head;
    while (fast.next && fast.next.next) {
        slow = slow!.next;
        fast = fast.next.next;
    }

    let secondHalf: ListNode | null = slow!.next;
    slow!.next = null;  // 첫 번째 절반의 끝을 표시
    
    // 두 번째 절반 뒤집기
    let prev: ListNode | null = null;
    let curr: ListNode | null = secondHalf;
    while (curr) {
        const nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    secondHalf = prev;

    // 두 리스트를 병합
    let first: ListNode | null = head;
    let second: ListNode | null = secondHalf;
    while (second) {
        // 임시 저장
        const firstNext = first!.next;
        const secondNext = second.next;

        // 노드 재연결
        first!.next = second;
        second.next = firstNext;

        // 포인터 이동
        first = firstNext;
        second = secondNext;
    }
}