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.
Fig 1: Middle node in singly 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.
Fig 2: Slow and fast reference in a single linked list

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
middle mid point node single linked list
Fig 3: Slow and fast reference traversing single linked list

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.
Fig 4: Slow reference pointing middle node in a single linked list

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

 

Scroll to Top