How to find the mid of a singly linked list in a single traversal

Overview

Given a singly linked list, find the middle node/element of the list in a single traversal.

Example 1:

Input - 1 -> 2 -> 3 -> 4 -> 5
Output - 3

Example 2:

Input - 1 -> 2 -> 3 -> 4
Output - 3

If the list contains an even number of nodes, two elements can be the middle elements. The second middle element has to be considered as the middle element. In Example 2, 2 and 3 can both be middle elements, but 3 should be considered as the middle element.

Solution

This problem can be solved using two pointers that are initially pointing to the head node. Let’s name the two pointers as slow_ptr and fast_ptr.

The steps of the algorithm are as follows:

Initialize slow_ptr and fast_ptr to the head node.
Continue performing the following steps until the fast_ptr or the next element of fast_ptr reaches the end of the list:
1. Move the slow_ptr by one node.
2. Move the fast_ptr by two nodes.

By the time fast_ptr reaches the end of the list, slow_ptr will be pointing to the middle node of the list.

Time complexity: O(N)
Space complexity: O(1)

Example

public class Main{

    static class Node{
        int data;
        Node next;

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


    static class SLL{
        Node head;

        public SLL() {
            this.head = null;
        }

        public void pushFront(int data){
            Node node = new Node(data);
            node.next = head;
            head = node;
        }

        public void print(){
            Node temp = head;
            while(temp != null) {
                System.out.print(temp.data + " -> ");
                temp = temp.next;
            }
            System.out.println("NULL");
        }

        public void getMiddle(){
            if(head == null) {
                System.out.println("Empty list. Cannot get the middle node");
                return;
            }
            Node slowPtr = head;
            Node fastPtr = head;

            while(fastPtr != null && fastPtr.next != null){
                slowPtr = slowPtr.next;
                fastPtr = fastPtr.next.next;
            }

            System.out.println("The middle element is - " + slowPtr.data);
        }
    }

    public static void main(String[] args) {

        SLL sll = new SLL();
        sll.pushFront(5);
        sll.pushFront(4);
        sll.pushFront(3);
        sll.pushFront(2);

        System.out.println("Even number of nodes list:");
        sll.print();
        sll.getMiddle();

        System.out.println("----");
        System.out.println("Odd number of nodes list:");
        sll.pushFront(1);
        sll.print();
        sll.getMiddle();

    }
}

Mid of SLL in Java