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