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.

FileName:LinkedListMiddleNode.java

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 class LinkedListMiddleNode {
 // Method to find the middle node of a linked list
 public static ListNode findMiddleNode(ListNode head) {
 ListNode slow = head; // Pointer initially pointing to the head of the linked list
 ListNode fast = head; // Pointer initially pointing to the head of the linked list
 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 head = new ListNode(1);
 head.next = new ListNode(2);
 head.next.next = new ListNode(3);
 head.next.next.next = new ListNode(4);
 head.next.next.next.next = new ListNode(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.

FileName: LinkedListMiddleNode.java

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 class LinkedListMiddleNode {
 public static ListNode findMiddleNode(ListNode head) {
 int count = 0;
 ListNode current = head;
 // Count the number of nodes in the linked list
 while (current != null) {
 count++;
 current = current.next;
 }
 int middle = count / 2;
 current = head;
 // 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
 ListNode head = new ListNode(1);
 head.next = new ListNode(2);
 head.next.next = new ListNode(3);
 head.next.next.next = new ListNode(4);
 head.next.next.next.next = new ListNode(5);
 ListNode middleNode = findMiddleNode(head);
 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.

FileName: LinkedListMiddleNode.java

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 class LinkedListMiddleNode {
 public static ListNode findMiddleNode(ListNode head) {
 Stack<ListNode> stack = new Stack<>();
 ListNode current = head;
 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
 ListNode head = new ListNode(1);
 head.next = new ListNode(2);
 head.next.next = new ListNode(3);
 head.next.next.next = new ListNode(4);
 head.next.next.next.next = new ListNode(5);
 ListNode middleNode = findMiddleNode(head);
 System.out.println("Middle node value: " + middleNode.val);
 }
}

Output:

Middle node value: 3

Complexity:

The time complexity of this approach is O(N) because we need to traverse the linked list once to push nodes onto the stack. The space complexity is also O(N) since we store all the nodes in the stack.