700171. Middle of a Linked List
Easy
Finding Middle Element in a Linked List
Slug: finding-middle-element-in-a-linked-list
Difficulty: Easy
Topic Tags: Linked List, Data Structures
Company Tags: VMWare, Zoho, Flipkart, Morgan Stanley, Amazon, Microsoft, Samsung, Hike, Payu, MAQ Software, Adobe, Wipro, SAP Labs, Qualcomm, Nagarro, GE, Veritas, IgniteWorld, Netskope
Summary
This problem is about finding the middle element in a linked list. The key concept involved is traversing the linked list and stopping at the middle node.
Detailed Explanation
The approach to solve this problem is straightforward: traverse the linked list until we reach the middle node. To do this, we need to keep track of the number of nodes we've visited so far. When we reach the middle node, stop and return it.
Here's a step-by-step breakdown of the solution:
- Initialize two pointers:
slowandfast. Both start at the beginning of the linked list. - Move both pointers one node at a time. The
fastpointer moves twice as fast as theslowpointer. - When the
fastpointer reaches the end of the linked list, theslowpointer will be at the middle node (or one node before it, if the length is odd). - Return the node at which the
slowpointer stopped.
Time complexity: O(n), where n is the number of nodes in the linked list. Space complexity: O(1), as we only use a constant amount of space to store the pointers and variables.
Optimized Solutions
Java
public Node findMiddle(Node head) {
if (head == null) return null;
Node slow = head;
Node fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}