Find middle node of a linked list

Problem statement :- Middle element of linked list can be at even or odd position(depending on length of linked list).If size of list is 2n, even no of elements, middle node is at position n+1 and if size of list is n,odd no of elements, then middle element is  (n+1)/2.
Solution 1(Two iteration of list) - Find the length of linked list and traverse again from beginning of list up to half of the linked list(as described above). It is not an efficient approach, because of two iteration.

Solution 2(One iteration of list) - Use two reference, one fast reference and another one slower one. Fast reference moves with twice speed as slow reference. Traverse the linked list with both and the moment fast reference reaches at end of list , slow reference will be at middle of list.

Below is sample code which uses two references and find middle element of list(fast references - 2x  and slow references - x):-

private Node findMiddleElement(Node head) {   Node fast2Xreference = head;   Node slowXRefernce = head;   /* Loop until fast2xReference reaches end of list or last node */   while (fast2Xreference != null && fast2Xreference.next != null) {     slowXRefernce = slowXRefernce.next;     /* check whether, fast reference can go to next to next node */     if (fast2Xreference.next != null)       fast2Xreference = fast2Xreference.next.next;   }   return slowXRefernce; }

Time and space complexity :- Since each node is traversed only once so time complexity is O(n). Space complexity is constant O(1).

Below is complete sample program for finding middle of linked list-

package com.devinline.linkedlist;

public class FindMiddleElementOflInkedList {

private Node findMiddleElement(Node head) {
 Node fast2Xreference = head;
 Node slowXRefernce = head;
 /* Loop until fast2xReference reaches end of list or last node */
 while (fast2Xreference != null && fast2Xreference.next != null) {
  slowXRefernce = slowXRefernce.next;
  /* check whether, fast reference can go to next to next node */
  if (fast2Xreference.next != null)
   fast2Xreference = fast2Xreference.next.next;
 }
 return slowXRefernce;
}

 class Node {
  public int data;
  public Node next; // reference(handler) for next Node.

  public Node(int data) {
   this.data = data;
   this.next = null;
  }
 }

 public static void main(String[] args) {
  Node head1;
  Node head2;
  /* First linked list formation - odd number of elements */
  FindMiddleElementOflInkedList fml = new FindMiddleElementOflInkedList();
  Node node1 = fml.new Node(12);
  head1 = node1;
  Node node2 = fml.new Node(18);
  Node node3 = fml.new Node(172);
  Node node4 = fml.new Node(62);
  head1.next = node2;
  head1.next.next = node3;
  head1.next.next.next = node4;
  System.out.println("Even number of elements:-  "
    + "Middle element of linked list [12 18 172 62] is  "
    + +fml.findMiddleElement(head1).data);

  /* Second linked list formation - Even number of elements */
  FindMiddleElementOflInkedList fm2 = new FindMiddleElementOflInkedList();
  Node node12 = fm2.new Node(121);
  head2 = node12;
  Node node22 = fm2.new Node(8);
  Node node32 = fm2.new Node(72);
  Node node42 = fm2.new Node(162);
  Node node52 = fm2.new Node(32);
  Node node62 = fm2.new Node(245);
  head2.next = node22;
  head2.next.next = node32;
  head2.next.next.next = node42;
  head2.next.next.next.next = node52;
  head2.next.next.next.next.next = node62;
  System.out.println("Odd number of elements:-  "
    + "Middle element of linked list [8 72 162 32 245] is "
    + fml.findMiddleElement(head2).data);

 }

}

=============Sample output=================
Even number of elements:-  Middle element of linked list [12 18 172 62] is  172
Odd number of elements:-  Middle element of linked list [8 72 162 32 245] is 162
========================================

Another linked list problems which uses fast and slow references :-
1. To check, linked list has even or odd number of elements.