要素の削除

連結リストの操作において、先頭ノードと他のノードの削除処理は異なります。他のノードは前のノードを介して削除されますが、先頭ノードには前のノードが存在しません。

先頭ノードを削除するには、単にヘッドポインタを次のノードに移動します。しかし、この特別なケースを避けるためにダミーヘッドノードを使用すると、全てのノードで一貫した削除方法が適用できます。

public class ListNodeRemoval {
    
    public ListNode removeElements(ListNode head, int target) {
        if (head == null) return null;
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        ListNode current = head;
        
        while (current != null) {
            if (current.value == target) {
                prev.next = current.next;
            } else {
                prev = current;
            }
            current = current.next;
        }
        
        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode current = head;
        for (int i = 2; i <= 5; i++) {
            current.next = new ListNode(i);
            current = current.next;
        }
        
        ListNodeRemoval processor = new ListNodeRemoval();
        ListNode result = processor.removeElements(head, 3);
        
        current = result;
        while (current != null) {
            System.out.print(current.value + " ");
            current = current.next;
        }
    }
}

class ListNode {
    int value;
    ListNode next;
    
    ListNode() {}
    ListNode(int val) { this.value = val; }
    ListNode(int val, ListNode next) { 
        this.value = val; 
        this.next = next; 
    }
}

連結リストの設計

連結リストの基本操作（追加/削除/検索）を実装します。ダミーヘッドノードを使用することで、先頭への追加操作を特別扱いせずに処理できます。

public class LinkedListOperations {
    
    private ListNode dummyHead;
    private int size;
    
    public LinkedListOperations() {
        dummyHead = new ListNode(0);
        size = 0;
    }
    
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }
    
    public void addAtTail(int val) {
        addAtIndex(size, val);
    }
    
    public void addAtIndex(int index, int val) {
        if (index < 0) index = 0;
        if (index > size) return;
        
        ListNode prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        
        ListNode newNode = new ListNode(val);
        newNode.next = prev.next;
        prev.next = newNode;
        size++;
    }
    
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;
        
        ListNode prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        prev.next = prev.next.next;
        size--;
    }
    
    public int get(int index) {
        if (index < 0 || index >= size) return -1;
        
        ListNode current = dummyHead.next;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current.value;
    }
}

リスト反転

反転処理には反復法と再帰法の2つのアプローチがあります。反復法では3つのポインタ（prev/curr/next）を使用し、再帰法では前のノード情報を引数として渡します。

public class ListReversal {
    
    // 反復法
    public ListNode iterativeReverse(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
    
    // 再帰法
    public ListNode recursiveReverse(ListNode head) {
        return reverseHelper(null, head);
    }
    
    private ListNode reverseHelper(ListNode prev, ListNode curr) {
        if (curr == null) return prev;
        ListNode next = curr.next;
        curr.next = prev;
        return reverseHelper(curr, next);
    }
}

ノードのペア交換

ノードをペアで交換するには、3つのポインタを使用します。ダミーヘッドを起点として、終了条件は現在のノードまたは次のノードがnullになるまでです。

public class NodeSwapper {
    
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode current = dummy;
        
        while (current.next != null && current.next.next != null) {
            ListNode first = current.next;
            ListNode second = current.next.next;
            
            current.next = second;
            first.next = second.next;
            second.next = first;
            current = current.next.next;
        }
        return dummy.next;
    }
}

末尾からの削除

末尾からn番目の要素を削除するには、高速ポインタを低速ポインタよりn+1ノード先に進めます。高速ポインタが末尾に達した時点で、低速ポインタは削除位置の直前を指しています。

public class NthRemover {
    
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode fast = dummy;
        ListNode slow = dummy;
        
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }
        
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

循環リスト検出

循環リストの検出にはフロイドの循環検出アルゴリズムを使用します。高速ポインタと低速ポインタが一致した後、先頭と出会い頭から等速で進む別のポインタが循環開始点で出会います。

public class CycleDetector {
    
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            
            if (slow == fast) {
                ListNode ptr1 = head;
                ListNode ptr2 = slow;
                while (ptr1 != ptr2) {
                    ptr1 = ptr1.next;
                    ptr2 = ptr2.next;
                }
                return ptr1;
            }
        }
        return null;
    }
}