ノードのペアごとの交換

隣接するノード同士をペアで交換する問題では、ダミーノード（仮想の頭ノード）を使用することで、先頭ノードが変更される場合の処理を簡略化できます。ポインタの操作順序が重要であり、リンクが切れないように一時的な変数を使用して参照を保存する必要があります。

以下の実装では、`prev`ポインタが常に交換対象ペアの直前を指し示すように移動させながら、`first`と`second`のポインタをつなぎ替えています。

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        
        while (prev.next != null && prev.next.next != null) {
            ListNode first = prev.next;
            ListNode second = prev.next.next;
            
            // ポインタのつなぎ替え実行
            first.next = second.next;
            second.next = first;
            prev.next = second;
            
            // prevポインタを次のペアの直前へ進める
            prev = first;
        }
        return dummy.next;
    }
}

後ろからN番目のノードの削除

リストを2回走査する方法（長さを計測してから削除位置を求める）も可能ですが、高速ポインタ（Fast）と低速ポインタ（Slow）を利用した「2ポインタ法」を使うと、1回の走査で効率的に解決できます。

この手法では、最初に高速ポインタをN+1步先に進めておきます。その後、2つのポインタを同時に末尾まで進めると、低速ポインタは削除対象ノードの「直前」のノードで停止します。これにより、削除操作をシンプルに行えます。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode fast = dummy;
        ListNode slow = dummy;
        
        // fastポインタを(n+1)分進める
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }
        
        // fastとslowを同時に進める
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        
        // 削除対象のノードをスキップ
        slow.next = slow.next.next;
        
        return dummy.next;
    }
}

2つの連結リストの交点

2つの連結リストが交差しているかどうかを判定し、交点ノードを見つける問題です。リストの長さの差を計算してポインタを調整する方法もありますが、より洗練された解法として「ポインタのスイッチング」があります。

このアルゴリズムでは、2つのポインタAとBをそれぞれの先頭に置きます。ポインタが末尾に到達したら、相手のリストの先頭に移動させます。もし交差していれば、2つのポインタは移動距離が等しくなるタイミングで交点ノードで合流します。交差していない場合は、両方のポインタがnullで合流します。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        
        ListNode pA = headA;
        ListNode pB = headB;
        
        // ポインタが合流するまでループ
        while (pA != pB) {
            pA = (pA == null) ? headB : pA.next;
            pB = (pB == null) ? headA : pB.next;
        }
        
        return pA;
    }
}

連結リストのサイクルII（開始地点の特定）

リスト内にサイクル（環）が存在する場合、そのサイクルが開始するノードを特定するには、フロイドのサイクル検出アルゴリズム（亀とウサギのアルゴリズム）を応用します。

まず、低速ポインタ（1ステップ）と高速ポインタ（2ステップ）を使って、サイクル内での出会い点を見つけます。その後、どちらか一方のポインタを先頭に戻し、もう片方を出会い点に置いた状態で、今度は両方とも1ステップずつ進めます。この2つのポインタが再び合流する地点が、サイクルの開始ノードとなります。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) return null;
        
        ListNode slow = head;
        ListNode fast = head;
        
        // パート1: 出会い点を見つける
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                // 出会い点が見つかったらパート2へ
                ListNode entry = head;
                while (entry != slow) {
                    entry = entry.next;
                    slow = slow.next;
                }
                return entry;
            }
        }
        
        // サイクルが存在しない
        return null;
    }
}