Linked List

class Solution {
    // 例: [0, 1, 2, 3]  ->  [3, 2, 1, 0]
    reverseList(head: ListNode | null): ListNode | null {
        let prev: ListNode | null = null; // 反転済みの先頭
        let curr = head;                  // 今つなぎ替えるノード

        while (curr) {
            // ① 退避: 先に「この先」をつかむ。次行で curr.next は消える
            const next = curr.next;

            // ② 付け替え: 矢印を後ろ向きにする
            curr.next = prev;

            // ③ 前進: つかんでおいた next のおかげで、切ったあとも先へ進める
            prev = curr;
            curr = next;
        }

        return prev; // curr が null になったとき、prev は元の末尾 = 新しい先頭
    }
}

class Solution {
    // 例: list1 = [1, 2, 4], list2 = [1, 3, 5]  ->  [1, 1, 2, 3, 4, 5]
    mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
        const dummy = new ListNode(0); // 答えの1つ手前に置く見張り役
        let tail = dummy;              // できあがった部分の末尾

        // 両方に残りがあるあいだは、小さいほうを末尾につなぐ
        while (list1 && list2) {
            if (list1.val <= list2.val) {
                // 3行とも必要で、この順番でないと壊れる
                tail.next = list1;  // ① つなぐ: 今の末尾の後ろに list1 を置く（つながりを変えるのはこの行だけ）
                tail = list1;       // ② 進む: 末尾の印を、いまつないだ list1 へ移す（ないと次も同じ場所を上書き）
                list1 = list1.next; // ③ 次へ: list1 を次の候補へ（先にやると tail が1つ先を指してしまう）
                // 例: dummy → 1 で list1 = 3 のとき
                //   ① dummy → 1 → 3   ② tail = 3   ③ list1 = 3 の次
            } else {
                tail.next = list2;  // 同じく ① つなぐ
                tail = list2;       // ② 進む
                list2 = list2.next; // ③ 次へ
            }
        }

        // 片方が尽きたら、残りは丸ごとつなぐだけでいい（そこはもう昇順に並んでいる）
        tail.next = list1 ?? list2;

        return dummy.next; // dummy の次が本当の先頭
    }
}

class Solution {
    // 例: [1, 2, 3, 4] で末尾が 2 に戻る  ->  true
    hasCycle(head: ListNode | null): boolean {
        let slow = head; // 1歩ずつ
        let fast = head; // 2歩ずつ

        // fast が2歩進めるときだけ回す。fast.next を確かめないと fast.next.next で落ちる
        while (fast && fast.next) {
            slow = slow!.next;
            fast = fast.next.next;

            // 値ではなく「同じノードか」を比べる。値は別ノードでも重なりうる
            if (slow === fast) return true;
        }

        // fast が末尾（null）に着いた = 行き止まりがある = 循環なし
        return false;
    }
}

class Solution {
    // 例: [1, 2, 3, 4, 5]  ->  [1, 5, 2, 4, 3]
    reorderList(head: ListNode | null): void {
        if (!head) return;

        // ① 中央を探す。fast は slow の倍進むので、fast が末尾に着くと slow は真ん中にいる。
        //    fast を1つ先から始めると、前半と後半が同数に割れる（奇数なら前半が1つ多い）
        let slow = head;
        let fast = head.next;
        while (fast && fast.next) {
            slow = slow.next!;
            fast = fast.next.next;
        }
        // 開始   slow=1 fast=2
        // 1周目  slow=2 fast=4
        // 2周目  slow=3 fast=null（4 の2つ先は無い）-> ここで終了
        // slow は 3 で止まる。1,2,3 | 4,5 と分かれるので、3 がちょうど前半の末尾

        // ② 後半を切り離して反転する（18 と同じ3行）。
        //    slow は前半の末尾なので、その1つ先 slow.next がそのまま後半の先頭になる
        let second = slow.next; // 3 の次 = 4。後半の先頭をここでつかむ
        // つかんでから切る。逆にすると後半への入口が消えて辿れなくなる
        slow.next = null; // 前半 1 → 2 → 3 | 後半 4 → 5 の2本になる
        let prev: ListNode | null = null;
        while (second) {
            const next = second.next;

            second.next = prev;

            prev = second;
            second = next;
        }
        // 反転が終わると prev = 5 → 4。前半は 1 → 2 → 3 のまま

        // ③ 前半と、反転した後半を交互につなぐ。
        //    ② で切ったのは slow(=3) の矢印だが、slow は head から続く鎖の途中のノード。
        //    なので head から辿れるのも 1 → 2 → 3 までになっている（4, 5 へは行けない）
        let first: ListNode | null = head;
        second = prev;
        while (first && second) {
            // 上書きする前に、両方の「次」を退避する（18 と同じ罠）。
            // 型注釈は省けない。first = next1 と互いを参照して推論が堂々巡りになる（TS7022）
            const next1: ListNode | null = first.next;
            const next2: ListNode | null = second.next;

            first.next = second; // 前半のノードの後ろに、後半のノードを差し込む
            second.next = next1; // その後ろに、前半の次のノードを戻す

            first = next1;
            second = next2;
        }
        // 1周目  first=1 second=5（退避 next1=2 next2=4）-> 1 → 5 → 2
        // 2周目  first=2 second=4（退避 next1=3 next2=null）-> 2 → 4 → 3
        // 3周目に入る前に second=null になり終了 -> 1 → 5 → 2 → 4 → 3
    }
}