# Finding the Middle Node of a Linked List in Java

Finding the middle node of a linked list in Java refers to the process of determining the node that is located at the middle position of the linked list. A linked list is a data structure where each element (node) contains a value and a reference (link) to the next node in the list. The middle node is the one that is positioned approximately in the middle of the list, dividing it into two equal or almost equal parts.

Example 1:

Input:

Linked List: 1 -> 2 -> 3 -> 4 -> 5

Output:

Middle Node: 3

Explanation:

Here, we have to find the middle element of the given linked list. In this case, the number of elements n is odd, the last element of the linked list will be at index n-1. The first pointer will reach the end of the linked list after (n-1)/2 iterations. At this point, the position of the First Pointer will be (n-1)/2. Therefore, the Second Pointer will be pointing to the middle element of the linked list, represented as the Second Pointer = (n-1)/2.

## Approach: Two Pointer Technique

To find the middle node of a linked list in Java, we can use the "runner" technique, where we have two pointers moving through the linked list at different speeds. The fast pointer moves two steps at a time, while the slow pointer moves one step at a time. When the fast pointer reaches the end of the linked list, the slow pointer will be at the middle node.

```class ListNode {
int val; // Value stored in the node
ListNode next; // Reference to the next node in the linked list
ListNode(int val) {
this.val = val; // Initialize the value of the node
}
}
// Method to find the middle node of a linked list
public static ListNode findMiddleNode(ListNode head) {
while (fast != null && fast.next != null) {
slow = slow.next; // Move the slow pointer one step ahead
fast = fast.next.next; // Move the fast pointer two steps ahead
}
return slow; // Return the node pointed by the slow pointer (middle node)
}
public static void main(String[] args) {
// Create a sample linked list: 1 -> 2 -> 3 -> 4 -> 5
ListNode middleNode = findMiddleNode(head); // Find the middle node
System.out.println("Middle node value: " + middleNode.val); // Print the value of the middle node
}
}
```

Output:

`Middle node value: 3`

Complexity:

The Time Complexity of this algorithm is O(N). This algorithm iterates through the linked list with two pointers, slow and fast. The fast pointer moves two steps at a time, while the slow pointer moves one step at a time. In the worst case, when the fast pointer reaches the end of the linked list (or null), the slow pointer will be at the middle node.

Space Complexity is O(1). The algorithm only uses two pointers, slow and fast, to traverse the linked list. Regardless of the size of the linked list, the space used by the algorithm remains constant. Thus, the space complexity is O(1) (constant).

## Approach: Single Pointer Technique

Another approach to finding the middle node of a linked list is by using a single pointer and counting the number of nodes in the list. Once the count is determined, the pointer can be moved to the middle node.

```class ListNode {
int val; // Value stored in the node
ListNode next; // Reference to the next node in the linked list
ListNode(int val) {
this.val = val; // Initialize the value of the node
}
}
public static ListNode findMiddleNode(ListNode head) {
int count = 0;
// Count the number of nodes in the linked list
while (current != null) {
count++;
current = current.next;
}
int middle = count / 2;
// Move the pointer to the middle node
for (int i = 0; i < middle; i++) {
current = current.next;
}
return current;
}
public static void main(String[] args) {
// Create a sample linked list: 1 -> 2 -> 3 -> 4 -> 5
System.out.println("Middle node value: " + middleNode.val);
}
}
```

Output:

`Middle node value: 3`

Complexity:

The single pointer approach has a time complexity of O(N) since it requires traversing the linked list twice. once for counting the nodes and once for moving the pointer to the middle node. The space complexity remains O(1) as it only uses a constant amount of additional space.

## Approach: Using a Stack

To solve the problem of finding the middle node of a linked list using a stack approach, we can follow these steps: Traverse the linked list and push each node onto a stack. Calculate the length of the linked list by counting the number of nodes. Pop nodes from the stack until reaching the middle node (length/2) while updating a current pointer. Then Return the current pointer as the middle node.

```import java.util.Stack;
class ListNode {
int val; // Value stored in the node
ListNode next; // Reference to the next node in the linked list
ListNode(int val) {
this.val = val; // Initialize the value of the node
}
}
public static ListNode findMiddleNode(ListNode head) {
Stack<ListNode> stack = new Stack<>();
int length = 0;
// Push each node onto the stack and calculate the length
while (current != null) {
stack.push(current);
current = current.next;
length++;
}
int middle = length / 2;
// Pop nodes from the stack until reaching the middle node
while (middle > 0) {
stack.pop();
middle--;
}
return stack.pop();
}
public static void main(String[] args) {
// Create a sample linked list: 1 -> 2 -> 3 -> 4 -> 5
`Middle node value: 3`