Given a singly linked list, find the middle node/element of the list in a single traversal.
Example 1:
1 -> 2 -> 3 -> 4 -> 53Example 2:
1 -> 2 -> 3 -> 43If 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.
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:
slow_ptr and fast_ptr to the head node.fast_ptr or the next element of fast_ptr reaches the end of the list:
slow_ptr by one node.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.
O(N)O(1)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();}}