Finding middle point of the linked list: with O(1) time complexity possible!

Finding middle point of the linked list is a very popular problem in DSA problem solving.

Algorithm :

1. Add a tail pointer to the node

2. Set a counter to LList

3. add a head & tail pointer to the list

a. head pointer point to the first node of the linked list

b. tail pointer point to the last node of the linked list

1. Add a new node to the list - a. set the new counter by adding 1 to the the previous counter

b. Store it into the hashmap with
5.Too find the middle node -
a. Get the current counter and dividing it by 2 will give the middle index of the linked list
b. lookup into the hashmap to get the middle node into the hash map

• LNode-

• LList -

package dsa.llist;

import java.util.HashMap;

public class LList {
    public static LNode head = null;
    public static LNode tail = null;
    public static int counter=1;
    public static HashMap<Integer,LNode> map;

    public LList(){
        map = new HashMap<>();
    }


    public static int getCounter() {
        return counter;
    }

    public static void setCounter(int counter) {
        LList.counter = counter;
    }

    public static LNode getHead() {
        return head;
    }

    public static void setHead(LNode head) {
        LList.head = head;
    }

    public static LNode getTail() {
        return tail;
    }

    public static void setTail(LNode tail) {
        LList.tail = tail;
    }

    public static void main(String[] args) {
        LList list = new LList();

        addNodeAtEnd( 10);
        addNodeAtEnd(20);
        addNodeAtEnd(30);
        addNodeAtEnd(40);
        addNodeAtEnd(50);

        print();
        System.out.println(LList.getCounter());
        System.out.println(LList.map);
        System.out.println(LList.counter);
        System.out.println(map.get(LList.getCounter()/2));

    }


    //Time Complexity -> O(N)
    public static void print(){
        LNode curr = head;
            while (curr != null){
                System.out.println(curr+" ");
                curr = curr.next;
            }
    }

    /**
     *
     * @param head
     * @return
     */
    public static boolean isEmpty(LNode head){
        return  (head == null);
    }

    /**
     * @param data
     *
     * Time Complexity -> O(1) ->Constant Time Complexity
     */
    public static LNode addNodeAtEnd(int data){
        LNode curr = head;
        if (isEmpty(curr)){
            LNode tmp = new LNode(data);
            head = tmp;
            tail = tmp;
            map.put(getCounter(),tail);
        }else{

            LNode tmp = new LNode(data);
            LList.setCounter(LList.getCounter()+1);
            tail.next = tmp;
            tail = tmp;
            map.put(getCounter(),tail);
        }

        return  head;
    }

    /**
     *
     * @param index
     * @return
     */
    public LNode getIndexNode(int index){
        return map.getOrDefault(index,new LNode(0));
    }

    public LNode findMiddleNode(){
        return getIndexNode((getCounter()/2)+1);
    }
}

1. Just by calling findMiddleNode() will return the middle node of the linked list with having constant time complexity.

linkedlist #DSA

https://www.geeksforgeeks.org/community/post/54162/find-middle-point-of-the-linked-list-with-o-1-time-complexity/

Follow me on -
twitter -> @cosmoworld2025
medium -> https://thisissurajitmishra.medium.com/