Find middle element of a linked list

Find middle element of a linked list in Java

---

Given a singly linked list find middle of the linked list.

Find Nth node from last in a linked list

Lets understand the problem statement graphically and it will be more clear,

Algorithm

---

There are 2 approach to get middle element of Linked list.

Approach 1:

1. Initialize the counter = 0.  
2. Iterate through a linked list and increment counter till you encounter null. 
3. Once you got the length of linked list, say 7. Middle element of linked list is located at
   (length of linked list / 2) 7/2 = 3. 
4. Traverse the list again till (length of linked list / 2) and return the node at
   (length of linked list / 2).

Approach 2:
We can get the middle element of linked list in one pass, lets see how,

1. In this approach, we take 2 pointers, fastPointer and slowPointer and initialize both to list head.
2. Iterate through list and move slowPointer 1 node at a time and fastPointer 2 nodes at a time.
3. When fastPointer reaches end of list, slowPointer will be pointing to middle element of list.

Java Program to find middle element of Linked list using Approach 2

---

Node.java

package javabypatel;

public class Node{
 private int data;
 private Node next;
 public Node(int data, Node next) {
  this.data = data;
  this.next = next;
 }
 public Node(int data) {
  this.data = data;
 }
 public int getData() {
  return data;
 }
 public void setData(int data) {
  this.data = data;
 }
 public Node getNext() {
  return next;
 }
 public void setNext(Node next) {
  this.next = next;
 }
}

GetMiddleOfLinkedList.java

package javabypatel;

public class GetMiddleOfLinkedList {

 public static void main(String[] args) {
  new GetMiddleOfLinkList();
 }

 public GetMiddleOfLinkedList() {
  Node startNode = new Node(10);
  Node temp2 = new Node(20);
  Node temp3 = new Node(30);
  Node temp4 = new Node(40);
  Node temp5 = new Node(50);
  Node temp6 = new Node(60);
  Node temp7 = new Node(70);
  Node temp8 = new Node(80);

  startNode.setNext(temp2);
  temp2.setNext(temp3);
  temp3.setNext(temp4);
  temp4.setNext(temp5);
  temp5.setNext(temp6);
  temp6.setNext(temp7);
  temp7.setNext(temp8);

  Node temp = findMiddleNodeOfLinkedList(startNode);
  System.out.println(temp.getData());
 }

 private Node findMiddleNodeOfLinkedList(Node startNode) {
  if(startNode==null){
   return startNode;
  }

  Node slowPointer = startNode;
  Node fastPointer = startNode;
  while(fastPointer!=null && fastPointer.getNext()!=null && fastPointer.getNext().getNext()!=null){
   slowPointer = slowPointer.getNext();
   fastPointer = fastPointer.getNext().getNext();

  }
  return slowPointer;
 }
}

You may also like to see

---

Detect loop in linked list

Reverse Linked list in Java

Find Nth node from last in a linked list

Sort Linked list.

Clone Linked list.

How is ambiguous overloaded method call resolved in java

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.