Problem Statement
You are given the head of a linked list, write a program to Find middle element in linked list. When there are even number of nodes in linked list, then there would be two middle nodes, return the second middle node.
Example
Input-1
head: 1->2->3->4->5
Output-1
3
Explanation
Here, 3 is the middle node of the linked list as shown below.
Input-2
head: 1->2->3->4->5->6
Output-2
4
Explanation
Here, there are even number of nodes in linked list, So there would be two middle nodes 3 and 4, we will return the second middle node i.e 4 as shown below.
Constraints
The number of nodes in the linked list is in the range [1 to 100].
1 <= Node.val <= 100
Algorithm 1 – Brute-Force approach – Using Extra Memory
Intuition:
The naive approach is to use the extra space as an array, store all the linked list node into the array maintaining the same order. After adding all the nodes into an array the size becomes equal to the length of the linked list, Now simply return the middle element of the array by using index count/2.
Algorithm
- Create a list of types ListNode temp to store all the nodes.
- Initialize a count variable to count the number of nodes.
- Traverse through the linked list using a while loop.
- Also, keep inserting the node values to the extra array from the linked list until we reach the NULL pointer.
- Now return the count/2 ^th^ index element from the list of ListNode.
Code Implementation
Code in C++
// Brute-Force approach to find middle of linked list
#include<bits/stdc++.h>
using namespace std;
//Definition for singly-linked list.
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
ListNode* middleNode(ListNode* head) {
vector<ListNode*> temp;
//created a vector of type ListNode pointer temp to store the nodes.
int count = 0;
//count variable.
while(head!=NULL){
temp.push_back(head);
//we keep inserting the elements from the linked-list
// untill we reach NULL pointer.
head=head->next;
count++;
}
return temp[count/2];
}
int main(){
//creating a new Linked-List.
ListNode* list = new ListNode();
ListNode* head = list;
for(int i =1;i<=5;i++){
list->next = new ListNode(i);
list = list->next;
}
ListNode* ans = middleNode(head->next);
cout<<ans->val<<endl;
return 0;
}
Code in Java
// Brute-Force approach to find middle of linked list
import java.util.*;
class Main{
public static class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public static ListNode middleElements(ListNode head){
//create a list of type ListNode temp to store the nodes.
List<ListNode> list = new ArrayList<>();
// count length
int count =0;
while (head!=null){
list.add(head);
//we keep inserting the elements from the linked-list
// until we reach NULL pointer.
head = head.next;
count++;
}
// return the middle item of the list
return list.get(count/2);
}
public static void main(String[] args) {
// create a list node and add next nodes
ListNode listNode = new ListNode();
ListNode head = listNode;
for(int i =1;i<=5;i++){
listNode.next = new ListNode(i);
listNode = listNode.next;
}
System.out.println(middleElements(head.next).val);
}
}
Code in Python
# Brute-Force approach to find middle of linked list
class Solution:
def middleNode(self, head: ListNode) -> ListNode:
arr = [head]
while arr[-1].next:
arr.append(arr[-1].next)
return arr[len(arr) // 2]
Output
3
Time Complexity
The time complexity is O(n). Since we are traversing the linked list only once to find middle element of linked list.
Space Complexity
The space complexity is O(n). Since extra space is used in the Program to Find middle element in linked list for storing all the nodes in a list of size n.
Algorithm 2 – By Counting Nodes – Double traversal
Intuition:
One intuition is to traverse through the Linked List while maintaining a count of nodes. After counting n total number of nodes, traverse the linked list once again but only up to the n/2^th^ node and return this node. It is better than previous approach as this algorithm does not use extra memory.
Algorithm
- Initialize a count variable to count the number of nodes.
- Traverse through all the linked list nodes using a while loop and count the total number of nodes.
- Initialize a ListNode middle to count the number of nodes.
- Now traverse through the linked list once again using a while loop which runs until i < n/2 and iterates over the linked list.
- At the end of the loop, return the middle node.
Code Implementation
Code in C++
// Double traversal approach to find middle of linked list
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* next;
};
class NodeOperation {
public:
// Function to add a new node
void pushNode(class Node** head_ref, int data_val)
{
// Allocate node
class Node* new_node = new Node();
// Put in the data
new_node->data = data_val;
// Link the old list off the new node
new_node->next = *head_ref;
// move the head to point to the new node
*head_ref = new_node;
}
/* Utility Function to find length of linked list */
int getLen(class Node* head){
int len = 0;
class Node* temp = head;
while (temp) {
len++;
temp = temp->next;
}
return len;
}
void printMiddle(class Node* head){
if (head) {
// find length
int len = getLen(head);
class Node* temp = head;
// traverse till we reached half of length
int midIdx = len / 2;
while (midIdx--) {
temp = temp->next;
}
// temp will be storing middle element
cout << temp->data << endl;
}
}
};
// Main Code
int main(){
class Node* head = NULL;
class NodeOperation* temp = new NodeOperation();
for (int i = 5; i > 0; i--) {
temp->pushNode(&head, i);
}
temp->printMiddle(head);
return 0;
}
Code in Java
// Double traversal approach to find middle of linked list
class Main {
Node head;
/*Creating a new Node*/
class Node {
int data;
Node next;
public Node(int data)
{
this.data = data;
this.next = null;
}
}
/*Function to add a new Node*/
public void pushNode(int data)
{
Node new_node = new Node(data);
new_node.next = head;
head = new_node;
}
/*Finding the length of the list.*/
public int getLen()
{
int length = 0;
Node temp = head;
while (temp != null) {
length++;
temp = temp.next;
}
return length;
}
/*Printing the middle element of the list.*/
public void printMiddle()
{
if (head != null) {
int length = getLen();
Node temp = head;
int middleLength = length / 2;
while (middleLength != 0) {
temp = temp.next;
middleLength--;
}
System.out.print(temp.data);
System.out.println();
}
}
public static void main(String[] args)
{
Main list = new Main();
for (int i = 5; i >= 1; i--) {
list.pushNode(i);
}
list.printMiddle();
}
}
Code in Python
# Double traversal approach to find middle of linked list
class Node:
def __init__(self, data):
self.data = data
self.next = None
class NodeOperation:
# Function to add a new node
def pushNode(self, head_ref, data_val):
# Allocate node and put in the data
new_node = Node(data_val)
# Link the old list off the new node
new_node.next = head_ref
# move the head to point to the new node
head_ref = new_node
return head_ref
def getLen(self, head):
temp = head
len = 0
while (temp != None):
len += 1
temp = temp.next
return len
def printMiddle(self, head):
if head != None:
# find length
len = self.getLen(head)
temp = head
# traverse till we reached half of length
midIdx = len // 2
while midIdx != 0:
temp = temp.next
midIdx -= 1
# temp will be storing middle element
print(temp.data)
# Driver Code
head = None
temp = NodeOperation()
for i in range(5, 0, -1):
head = temp.pushNode(head, i)
temp.printMiddle(head)
Output
3
Time Complexity
The time complexity is O(n). Since we are traversing the linked list two times to find middle element of linked list.
Space Complexity
The space complexity is O(1). Since no extra space is used in the Program to Find middle element in linked list.
Algorithm 3 – Efficient Approach – Using Slow and Fast Pointers
Intuition:
The efficient approach is to traverse through the linked list using two-pointers i.e slow pointer and fast pointer. Increment slow_ptr by 1 step and fast_ptr by 2 steps, As a result, the fast pointer will travel double than that of the slow pointer. So When the fast pointer will reach to the end of the linked list, slow point would still be at the middle of the linked list. Think!
This approach is efficient and better than the previous approaches because only single traversal is needed in this algorithm without using extra memory.
Algorithm
- Initialize two pointers slow_ptr and fast_ptr and point both of them to the head node.
- Until fast_ptr is NULL or the next of fast_ptr is NULL, move slow_ptr by one step and fast_ptr by two steps at the same time.
- As we can see slow_ptr is pointing towards the middle of the Linked List. Hence return the slow_ptr.
Code Implementation
Code in C++
// Efficient approach to find middle of linked list
#include <iostream>
using namespace std;
class Node{
public:
int data;
Node *next;
};
class NodeOperation{
public:
// Function to add a new node
void pushNode(class Node** head_ref,int data_val){
// Allocate node
class Node *new_node = new Node();
// Put in the data
new_node->data = data_val;
new_node->next = *head_ref;
*head_ref = new_node;
}
void printMiddle(class Node *head){
struct Node *slow_ptr = head;
struct Node *fast_ptr = head;
if (head!=NULL)
{
while (fast_ptr != NULL && fast_ptr->next != NULL)
{
fast_ptr = fast_ptr->next->next;
slow_ptr = slow_ptr->next;
}
cout << slow_ptr->data << endl;
}
}
};
// Main method
int main(){
class Node *head = NULL;
class NodeOperation *temp = new NodeOperation();
for(int i=5; i>0; i--){
temp->pushNode(&head, i);
}
temp->printMiddle(head);
return 0;
}
Code in Java
// Efficient approach to find middle of linked list
class LinkedList{
Node head;
// Linked list node
class Node{
int data;
Node next;
Node(int d){
data = d;
next = null;
}
}
// Function to find the middle of linked list
void printMiddle(){
Node slow_ptr = head;
Node fast_ptr = head;
while (fast_ptr != null && fast_ptr.next != null){
fast_ptr = fast_ptr.next.next;
slow_ptr = slow_ptr.next;
}
System.out.println(slow_ptr.data);
}
// Inserts a new Node at front of the list.
public void push(int new_data){
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
}
class Main{
public static void main(String [] args){
LinkedList list = new LinkedList();
for (int i=5; i>0; --i){
list.push(i);
}
list.printMiddle();
}
}
Code in Python
# Efficient approach to find middle of linked list
# Node class
class Node:
# Function to initialise the node object
def __init__(self, data):
self.data = data
self.next = None
# Linked List class contains a Node object
class LinkedList:
def __init__(self):
self.head = None
# Function to insert a new node at the beginning
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
# Function that find the middle element.
def printMiddle(self):
# slow pointer will go one step a time,
# fast will go two at a time
slow = self.head
fast = self.head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# return middle element data
print(slow.data)
# Main code
if __name__=='__main__':
list = LinkedList()
for i in range(5, 0, -1):
list.push(i)
list.printMiddle()
Output
3
Time Complexity
The time complexity is O(n). Since we are traversing the linked list once to find middle element of linked list.
Space Complexity
The space complexity is O(1). Since no extra space is used in the Program to Find middle element in linked list.
Conclusion
- We have given the head of a singly linked list, we had to write a program to Find middle element in linked list.
- If there were even number of nodes in linked list, then there would have two middle nodes, we had to return the second middle node.
- For eg, A linked list is given 1->2->3->4->5, here the middle of list is 3.
- The naive approach takes O(n) time complexity as two traversals were needed, and O(n) space complexity because an array was used as an extra space.
- On the other hand, the most efficient approach to Find middle element in linked list Using Slow and Fast Pointers takes O(n) time complexity and O(1) as space complexity.
- if we increment a slow_ptr by 1 step and fast_ptr by 2 steps and when the fast pointer will reach at the end, the slow pointer will be at the middle of linked list.
FAQ
Q. Will the above approaches work if the linked link has a loop?
A. No, if the linked list has a loop, the traversal will not be possible and the pointer will be stuck in a cyclic loop forever. Hence gives a Time Limit Exceed error.
Q. How do we modify the above code to delete the middle node?
A. Instead of returning the middle of the linked list just update the middle node’s value with the value of its next node, and finally point the next node of the middle node to the next of next node.
Q. Can we solve the above problem with some different approach?
A. Yes, Initialize the middle pointer as head and traverse through the list from the head, When the counter is odd while traversing, increase the counter and change mid to mid->next. So the middle pointer will travel only half of the size of the list.
Q. What are some similar coding questions of Linked List.
A. Refer Detect Loop in Linked List Refer Remove Nth Node from List End Refer Reverse a Linked List
