リンクリストの前半を反転させてから、後半と連結する

この問題は 2 つのアルゴリズム問題に分けることができます：[リンクリストの中間ノード] と [リンクリストの反転]。

リンクリストの中間ノード（双指針）#

速いポインタ fast と遅いポインタ slow を使って、[速いポインタ fast ] は毎回 2 ステップ進み、[遅いポインタ slow ] は毎回 1 ステップ進みます。

fast のステップ数は常に slow の 2 倍です。したがって、速いポインタがリンクリストを走り終えたとき、遅いポインタはリンクリストの中間ノードを指します。偶数の長さのリンクリストには2 つの中間ノードがあるため、2 つのケースを考慮する必要があります：

リンクリストの長さが奇数：fast がリンクリストの [尾ノード] に到達したとき、slow はちょうど [中間ノード] に到達します。
リンクリストの長さが偶数：fast が [null] に到達したとき（[尾ノード] を越えた後）、slow はちょうど [2 番目の中間ノード] に到達します。

以上の規則をまとめると、fast が尾ノードに出会うか越えたときにループを抜け、slow を返すだけで済みます。

// 長さが奇数のリンクリスト
ListNode oddHead = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, null)))));
// 長さが偶数のリンクリスト
ListNode evenHead = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, new ListNode(6, null))))));

Console.WriteLine("odd head middleNode val: {0}", MiddleNode(oddHead).Val);
Console.WriteLine("even head middleNode val: {0}", MiddleNode(evenHead).Val);

// リンクリストの中間ノード
ListNode MiddleNode(ListNode head)
{
    // 初期化：速いポインタと遅いポインタはリンクリストの頭ノード head を指します
    ListNode? fast = head, slow = head;

    // 速いポインタが尾ノードを越えたときにループを抜けます
    while (fast != null && fast.Next != null)
    {
        fast = fast.Next.Next;
        slow = slow!.Next;
    }

    return slow!;
}

class ListNode
{
    public int Val { get; set; }
    public ListNode? Next { get; set; }
    public ListNode(int val, ListNode? next)
    {
        Val = val;
        Next = next;
    }
}

もし問題が「最初の中間ノード」を返すことを要求する場合、fast が尾ノードまたはその前のノードに出会ったときにループを抜ける必要があります。この場合、判断条件を while fast.next and fast.next.next に変更すればよいです。

リンクリストの反転#

解法一：反復（双指針）#

リンクリストを走査し、各ノードにアクセスする際に next 参照を変更します。具体的な流れはコードのコメントを参照してください。

// リンクリストの初期化
ListNode node = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, null)))));

ListNode reverseNode = ReverseNode(node);
while (reverseNode != null)
{
    Console.WriteLine("reverseNode val: {0}", reverseNode.Val);
    reverseNode = reverseNode.Next;
}

// リンクリストの反転：反復（双指針）
ListNode ReverseNode(ListNode head)
{
    // 初期化：pre, cur はそれぞれ null と頭ノードを指します
    ListNode pre = null, cur = head;
    while (cur != null)
    {
        ListNode tmp = cur.Next; // 後続ノードを一時保存

        cur.Next = pre;          // 参照を変更
        pre = cur;               // 現在のノードを一時保存

        cur = tmp;               // 次のノードにアクセス
    }

    return pre;
}

class ListNode
{
    public int Val { get; set; }
    public ListNode? Next { get; set; }
    public ListNode(int val, ListNode? next)
    {
        Val = val;
        Next = next;
    }
}

最終コード#

// Q: リンクリストの前半を反転し、後半と接続する

// 長さが奇数のリンクリストを初期化
using System.Diagnostics;

ListNode oddHead = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, null)))));
// 長さが偶数のリンクリストを初期化
ListNode evenHead = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, new ListNode(6, null))))));

// 要求に従ってリンクリストの前半を反転し、後半と接続したリンクリスト
Console.WriteLine("長さが奇数のリンクリスト：");

Stopwatch sw = Stopwatch.StartNew();
ListNode? finalOddHead = ReverseLeftOfMiddleAndCombineRightOfMiddle(oddHead);
sw.Stop();
Console.WriteLine($"時間: {sw.ElapsedMilliseconds}ms");

while (finalOddHead != null)
{
    Console.WriteLine(finalOddHead.Val);
    finalOddHead = finalOddHead.Next;
}

// 要求に従ってリンクリストの前半を反転し、後半と接続したリンクリスト
Console.WriteLine("長さが偶数のリンクリスト：");

sw = Stopwatch.StartNew();
ListNode? finalEvenHead = ReverseLeftOfMiddleAndCombineRightOfMiddle(evenHead);
sw.Stop();
Console.WriteLine($"時間: {sw.ElapsedMilliseconds}ms");

while (finalEvenHead != null)
{
    Console.WriteLine(finalEvenHead.Val);
    finalEvenHead = finalEvenHead.Next;
}

ListNode ReverseLeftOfMiddleAndCombineRightOfMiddle(ListNode head)
{
    // リンクリストの中点を見つける
    // 速いポインタと遅いポインタを使用し、速いポインタは毎回2ステップ進み、速いポインタのステップ数は遅いポインタの2倍、遅いポインタは毎回1ステップ進み、速いポインタが出会うか越えたときにループを抜け、slow を返します。これが中間ノードを表します。
    ListNode fast = head, slow = head;
    while (fast != null && fast.Next != null)
    {
        fast = fast.Next.Next;
        slow = slow.Next;
    }

    // リンクリストの長さが奇数の場合、slow はちょうど最中間のノードです
    // リンクリストの長さが偶数の場合、slow は中間の2つのノードの最後のノードです
    ListNode middleNode = slow;

    // 左側のリンクリストを反転
    // 反復（双指針）を使用
    // ここで pre を中点に指し、最後に左側のリンクリストを反転した後、左側のリンクリストの最後のノードが右側のリンクリスト（リンクリストの中点）を指すようにします。
    ListNode pre = middleNode, cur = head;
    // 現在のループのノードが null でなく、現在のループのノードが中点の前である限り、つまり中点の左側のリンクリストのみを反転します
    while (cur != null && cur.Val != middleNode.Val)
    {
        // 後続ノードを一時保存
        ListNode tmp = cur.Next;

        // 参照を変更
        cur.Next = pre;
        // 現在のノードを一時保存
        pre = cur;

        // 次のノードにアクセス
        cur = tmp;
    }

    return pre;
}

// 単方向リンクリスト構造
class ListNode
{
    public int Val { get; set; }
    public ListNode? Next { get; set; }
    public ListNode(int val, ListNode? next)
    {
        Val = val;
        Next = next;
    }
}

myEsn2E9