Find midpoint/middle node of single linked list non recursive algorithm -java

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

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

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

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

Step 1:

Step 2:

Step 3:

Program – find middle or midpoint of single linked in java

1.) FindMiddleNode Class:

2.) Client Class:

3.) Node Class:

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

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

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

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

Step 1:

Step 2:

Step 3:

Program – find middle or midpoint of single linked in java

1.) FindMiddleNode Class:

2.) Client Class:

3.) Node Class:

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

You may also like: