Approach 2 (Slow and fast pointer approach)
We use the concept of slow and fast pointer to find the middle element of array or list. We declare two pointers slow and fast for linked list and two variables slow and fast for arrays. Initially both slow and fast points to starting element of array or list. Increase slow pointer by 1 and increase fast pointer by 2. Traverse until fast reaches to end of array or list. then traverse again fast pointing to start and Return the slow pointer node as middle element of list or array.
Example
Below is the Implementation of the above approach:
#include <iostream>
#include <vector>
using namespace std;
// Definition of a ListNode for linked list (if using linked
// list)
struct ListNode {
int val;
ListNode* next;
ListNode(int x)
: val(x)
, next(NULL)
{
}
};
// Function to find the middle element of an array using
// slow and fast pointers
int findMiddle(vector<int>& nums)
{
int slow = 0, fast = 0;
while (fast < nums.size() && fast + 1 < nums.size()) {
slow++;
fast += 2;
}
return nums[slow];
}
// Function to find the middle element of a linked list
// using slow and fast pointers
int findMiddle(ListNode* head)
{
ListNode* slow = head;
ListNode* fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
return slow->val;
}
int main()
{
// Example usage with array
vector<int> nums = { 1, 2, 3, 4, 5 };
cout << "Middle element of array: " << findMiddle(nums)
<< endl;
// Example usage with linked list
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);
cout << "Middle element of linked list: "
<< findMiddle(head) << endl;
return 0;
}
import java.util.*;
// Definition of a ListNode for linked list (if using linked
// list)
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Main {
// Function to find the middle element of an array using
// slow and fast pointers
public static int findMiddle(List<Integer> nums)
{
int slow = 0, fast = 0;
while (fast < nums.size()
&& fast + 1 < nums.size()) {
slow++;
fast += 2;
}
return nums.get(slow);
}
// Function to find the middle element of a linked list
// using slow and fast pointers
public static int findMiddle(ListNode head)
{
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow.val;
}
public static void main(String[] args)
{
List<Integer> nums = Arrays.asList(1, 2, 3, 4, 5);
System.out.println("Middle element of array: "
+ findMiddle(nums));
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);
System.out.println("Middle element of linked list: "
+ findMiddle(head));
}
}
# Python program for the above approach
# Definition of a ListNode for linked list
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
# Function to find the middle element of an array using slow and fast pointers
def findMiddle(nums):
slow = 0
fast = 0
while fast < len(nums) and fast + 1 < len(nums):
slow += 1
fast += 2
return nums[slow]
# Function to find the middle element of a linked list using slow and fast pointers
def findMiddleLinkedList(head):
slow = head
fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
return slow.val
# Main function
if __name__ == "__main__":
nums = [1, 2, 3, 4, 5]
print("Middle element of array:", findMiddle(nums))
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
print("Middle element of linked list:", findMiddleLinkedList(head))
# This code is contributed by Susobhan Akhuli
using System;
using System.Collections.Generic;
public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}
public class Program {
// Function to find the middle element of an array using
// slow and fast pointers
static int FindMiddle(List<int> nums)
{
int slow = 0, fast = 0;
while (fast < nums.Count && fast + 1 < nums.Count) {
slow++;
fast += 2;
}
return nums[slow];
}
// Function to find the middle element of a linked list
// using slow and fast pointers
static int FindMiddle(ListNode head)
{
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow.val;
}
public static void Main(string[] args)
{
// Example usage with array
List<int> nums = new List<int>{ 1, 2, 3, 4, 5 };
Console.WriteLine("Middle element of array: "
+ FindMiddle(nums));
// Example usage with linked list
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);
Console.WriteLine("Middle element of linked list: "
+ FindMiddle(head));
}
}
// JavaScript program for the above approach
// Definition of a ListNode for linked list
class ListNode {
constructor(val) {
this.val = val;
this.next = null;
}
}
// Function to find the middle element of an array
function findMiddleArray(nums) {
let slow = 0, fast = 0;
while (fast < nums.length && fast + 1 < nums.length) {
slow++;
fast += 2;
}
return nums[slow];
}
// Function to find the middle element of a linked list
function findMiddleLinkedList(head) {
let slow = head;
let fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
return slow.val;
}
// Example usage with array
let nums = [1, 2, 3, 4, 5];
console.log("Middle element of array:", findMiddleArray(nums));
// Example usage with linked list
let 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);
console.log("Middle element of linked list:", findMiddleLinkedList(head));
// This code is contributed by Susobhan Akhuli
Output
Middle element of array: 3 Middle element of linked list: 3
This approach of finding middle element is contributed by Ayush Mishra.
Find the Middle Element of an Array or List
Given an array or a list of elements. The task is to find the middle element of given array or list of elements. If the array size is odd, return the single middle element. If the array size is even, return the two middle elements.
Example
Input: arr = {1, 2, 3, 4, 5}
Output: 3Input: arr = {7, 8, 9, 10, 11, 12}
Output: 9 10
Approach:
Check the length of array is even or odd. For odd array length the middle element would be arr[length/2]. Otherwise, two middle element that is: arr[length/2] and arr[length/2 -1]
Below is the implementation of the above approach:
import java.util.*;
public class Main {
// Function to find middle element(s) of a list
static List<Integer>
findMiddleElements(List<Integer> arr)
{
List<Integer> result = new ArrayList<>();
int n = arr.size();
// Check if the size of the list is even or odd
if (n % 2 == 0) {
// If even, push two middle elements into the
// result list
result.add(arr.get(n / 2 - 1));
result.add(arr.get(n / 2));
}
else {
// If odd, push the single middle element into
// the result list
result.add(arr.get(n / 2));
}
return result;
}
public static void main(String[] args)
{
// Sample list
List<Integer> arr = new ArrayList<>();
arr.add(1);
arr.add(2);
arr.add(3);
arr.add(4);
arr.add(5);
// Find middle elements using the function
List<Integer> middleElements
= findMiddleElements(arr);
// Display the middle element(s)
System.out.print("Middle Element(s): ");
for (int num : middleElements) {
System.out.print(num + " ");
}
System.out.println();
}
}
def find_middle_elements(arr):
result = []
n = len(arr)
# Check if the size of the list is even or odd
if n % 2 == 0:
# If even, append two middle elements to the result list
result.append(arr[n // 2 - 1])
result.append(arr[n // 2])
else:
# If odd, append the single middle element to the result list
result.append(arr[n // 2])
return result
if __name__ == "__main__":
# Sample list
arr = [1, 2, 3, 4, 5]
# Find middle elements using the function
middle_elements = find_middle_elements(arr)
# Display the middle element(s)
print("Middle Element(s):", end=" ")
for num in middle_elements:
print(num, end=" ")
print()
using System;
using System.Collections.Generic;
public class Program {
// Function to find middle element(s) of a list
static List<int> FindMiddleElements(List<int> arr)
{
List<int> result = new List<int>();
int n = arr.Count;
// Check if the size of the list is even or odd
if (n % 2 == 0) {
// If even, push two middle elements into the
// result list
result.Add(arr[n / 2 - 1]);
result.Add(arr[n / 2]);
}
else {
// If odd, push the single middle element into
// the result list
result.Add(arr[n / 2]);
}
return result;
}
public static void Main(string[] args)
{
// Sample list
List<int> arr = new List<int>{ 1, 2, 3, 4, 5 };
// Find middle elements using the function
List<int> middleElements = FindMiddleElements(arr);
// Display the middle element(s)
Console.Write("Middle Element(s): ");
foreach(int num in middleElements)
{
Console.Write(num + " ");
}
// Keep the console window open in debug mode.
Console.WriteLine();
}
}
function findMiddleElements(arr) {
let result = [];
let n = arr.length;
// Check if the size of the array is even or odd
if (n % 2 === 0) {
// If even, append two middle elements to the result array
result.push(arr[n / 2 - 1]);
result.push(arr[n / 2]);
} else {
// If odd, append the single middle element to the result array
result.push(arr[Math.floor(n / 2)]);
}
return result;
}
// Sample array
let arr = [1, 2, 3, 4, 5];
// Find middle elements using the function
let middleElements = findMiddleElements(arr);
// Display the middle element(s)
console.log("Middle Element(s):", middleElements.join(" "));
#include <iostream>
#include <vector>
using namespace std;
// Function to find middle element(s) of a vector
vector<int> findMiddleElements(const vector<int>& arr)
{
vector<int> result;
int n = arr.size();
// Check if the size of the vector is even or odd
if (n % 2 == 0) {
// If even, push two middle elements into the result vector
result.push_back(arr[n / 2 - 1]);
result.push_back(arr[n / 2]);
}
else {
// If odd, push the single middle element into the result vector
result.push_back(arr[n / 2]);
}
return result;
}
int main()
{
// Sample vector
vector<int> arr = { 1, 2, 3, 4, 5 };
// Find middle elements using the function
vector<int> middleElements = findMiddleElements(arr);
// Display the middle element(s)
cout << "Middle Element(s): ";
for (int num : middleElements) {
cout << num << " ";
}
return 0;
}
Output
Middle Element(s): 3
Time Complexity: O(1)
Auxiliary Space: O(1)