LinkedList is a collection of the independent nodes which connected to each other using their pointer address i.e. next and previous. LinkedList is dynamic in nature unlike an array fixed-size data structure. LinkedList increases their size on runtime as the new node is created and linked with each either in stack format or queue format using reference pointer addresses.
In this article, we discussed a problem: How to find the middle element in LinkedList in O(n) time complexity means in single traverse. In this, we are using the Singly LinkedList.
In order to find the middle element (node), the better approach traverses the list with two pointers. One pointer which we call slow pointer, who traverse (iterate) the LinkedList one by one and Second pointer which we call fast pointer, who traverse (iterate) the LinkedList by moving two.
Suppose both pointers slow and fast are on the first node (head node). The slow pointer moves to the next node from the 1st node to 2nd node but fast node jump directly on the 1st node to the 3rd node. So, the slow pointer always covers half of nodes as compared to fast nodes in LinkedList elements because fast nodes are jumping twice as compared to slow nodes. Whenever fast node next pointer address is null then we have middle node (middle element).
Example:
In given singly LinkedList, 1⇒ 2 ⇒ 3 ⇒ 4 ⇒ 5.
The middle node is 3. This is an odd size, LinkedList.
In even size, LinkedList 1⇒ 2 ⇒ 3 ⇒ 4 ⇒ 5 ⇒ 6.
The middle node is 4.
public SinglyNode findMiddleNode(SinglyNode head) {
if(head==null)
return head;
else
System.out.println("HEAD NODE: "+head.data);
SinglyNode fast, slow;
fast = head;
slow = head;
while(fast!=null && fast.next!=null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}