Javaにおける単方向連結リストの中央ノードを効率的に検索する方法

2つのポインタを使用する方法:

• リストの中央ノードを見つけるために、2つのポインタを使用します。
• 1つのポインタを1つずつ進め、もう1つのポインタを2つずつ進めることで、リストをトラバースします。
• 2つ目のポインタがリストの末尾に到達したとき、1つ目のポインタは中央ノードに到達します。

public ListNode findMiddleNode(ListNode head) {
   ListNode slow = head;
   ListNode fast = head;
   while (fast != null && fast.next != null) {
       slow = slow.next;
       fast = fast.next.next;
   }
   return slow;
}

リストのサイズを事前に計算する方法:

• リストのサイズを事前に計算し、サイズの半分に相当するノードを見つけます。
• リストのサイズが奇数の場合、中央ノードが唯一のノードになります。
• リストのサイズが偶数の場合、中央ノードは2つありますが、どちらを返しても構いません。

public ListNode findMiddleNode(ListNode head) {
   int size = 0;
   ListNode current = head;
   while (current != null) {
       size++;
       current = current.next;
   }
   int middleIndex = size / 2;
   current = head;
   for (int i = 0; i < middleIndex; i++) {
       current = current.next;
   }
   return current;
}