Find midpoint / middle node of single linked list in java (example)

• Given a single linked list, find midpoint or middle node in a single linked list using java.
  • Traverse single linked list using non recursive or iterative algorithm.
• Find midpoint of Single linked list is shown in Fig 1.
  • There are five nodes in a single linked list
  • So node number 3 is the middle node of single linked list.

Algorithm – find middle or mid point of single linked list in java

• Use two references slow and fast
  • slow reference will jump by one node at a time.
    • In the above linked list, It will visit 1,2,3,4,5 nodes. i.e. all nodes
  • fast reference will jump twice as that of slow reference.
    • In above linked list, It will visit nodes number 1, 3 and 5
  • fast reference required three jumps to reach to end of list
• By the time fast reference reached end of list
  • slow reference reached middle of linked list
    • This is what we are looking for
      • slow reference will provide the middle node of single linked list.

Example – midpoint/middle node in single linked list using iterative algorithm

Let us apply above algorithm to single linked list to find middle node (example).

Step 1:  

• Create two references slow and fast.
• Both reference pointing to head of linked list as shown in Fig 2.

Step 2:

• slow reference will jump by 1
  • slow pointer will reach node number 2
• fast pointer will jump by 2
  • fast pointer will reach node number 3
• Refer Fig 3 for reference traversal

Step 3:

• Apply step 2 again.
• slow reference will reach node number 3.
• fast reference will reach node number 5.
  • which the end of linked list.
  • slow reference will give us middle node of single linked list.
• Refer Fig: 4 for details.

Time complexity of algorithm is O (n).

Program – find middle or midpoint of single linked in java

1.) FindMiddleNode Class:

• FindMiddleNode class is responsible for finding the middle node in a single linked list.
• Traverse the single linked list using iterative algorithm.

package org.learn.Question;

import org.learn.List.Node;

public class FindMiddleNode {
 public static Node findMiddleNode(Node head) {
  if (null == head) {
   System.out.println("Single linked list is empty");
   return null;
  }
  Node slow = head;
  Node fast = head;

  while (fast != null && fast.next != null) {
   slow = slow.next;
   fast = fast.next.next;
  }
  return slow;
 }

 public static void insert(Node head, int data) {
  while (head.next != null)
   head = head.next;
  head.next = new Node(data);
 }

 public static void print(Node head) {
  while (head != null) {
   System.out.printf("%d ", head.data);
   head = head.next;
  }
  System.out.println("");
 }
}

2.) Client Class:

• We are creating the single linked list in Client class
• Find the middle node of single linked list, by calling findMiddleNode method of FindMiddleNode class

package org.learn.Client;

import org.learn.List.Node;
import org.learn.Question.FindMiddleNode;

public class Client {
 public static void main(String[] args) {
  int[] data = { 1, 2, 3, 4, 5 };
  Node head = new Node(data[0]);

  for (int count = 1; count < data.length; count++)
   FindMiddleNode.insert(head, data[count]);

  System.out.printf("1.) Single linked list is : ");

  FindMiddleNode.print(head);
  Node middle = FindMiddleNode.findMiddleNode(head);
  if (null != middle) {
   System.out.printf("2.) Middle node is at position : %d", middle.data);
  }
 }
}

3.) Node Class:

• Node class is representing the node(s) of single linked list

package org.learn.List;

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

Output – find middle or midpoint of single linked list in java

1.) Single linked list is : 1 2 3 4 5 
2.) Middle node is at position : 3

Download code – Middle node/midpoint in single linked list java