Showing posts with label traverse the linked list only once to get middle node. Show all posts
Showing posts with label traverse the linked list only once to get middle node. Show all posts

Find the middle node of a given linked list

Given a singly linked list, find the middle NODE of the linked list. For example, if given linked list is 1->2->3->4->5 then output should be 3.
If there are even nodes, then there would be two middle nodes, we need to print second middle element. For example, if given linked list is 1->2->3->4->5->6 then output should be 4.
CONDITION:
  • Need to traverse the linked list only once. 


Find middle node of a given linked list



public class MiddleNode {

 class NODE {
  
  int data;
  NODE next;

  public NODE(int data) {
   this.data = data;
   this.next = null;
  }
 }
 
 public static void main(String[] args) {

  MiddleNode obj = new MiddleNode();

  int val[] = new int[] { 3, 6, 7, 8, 9, 11, 13, 15, 17, 22, 24, 25, 28};
  
  /* Create linked list */
  NODE start = obj.createLinkedList(val);
  
  /* Get middle NODE */
  NODE middleNode = obj.getMiddleNode(start);
  
  System.out.println("MIDDLE NODE : "+middleNode.data);
 }
 
 /*
  * Create linked base based on given array
  */
 public NODE createLinkedList(int val[]) {
  NODE start = null;
  for (int i : val) {
   NODE tmp = new NODE(i);
   if (start == null) {
    start = tmp;
   } else {
    NODE mover = start;
    while (mover.next != null) {
     mover = mover.next;
    }
    mover.next = tmp;
   }
  }
  return start;
 }
 
 /*
  * Getting middle NODE just by traversing only once
  */
 public NODE getMiddleNode(NODE start) {
  NODE slow = start, fast = start;
  while(fast.next != null && fast.next.next != null) {
   slow = slow.next;
   fast = fast.next.next;
  }
  if(fast.next != null) {
   slow = slow.next;
  }
  return slow;
 }
}

OUTPUT:


MIDDLE NODE : 13