Middle Node in a Linked List
Last Updated : 28 Aug, 2025
Given the head of singly linked list, find middle node of the linked list.
- If the number of nodes is odd, return the middle node.
- If the number of nodes is even, there are two middle nodes, so return the second middle node.
Example:
Input:
Output: 3
Explanation: There are 5 nodes in the linked list and there is one middle node whose value is 3.
Input:
Output: 40
Explanation: There are 6 nodes in the linked list, so we have two middle nodes: 30 and 40, but we will return the second middle node which is 40.
[Naive Approach] Two Passes - O(n) Time and O(1) Space
The idea is to traverse the entire linked list once to count the total number of nodes. After determining the total count, traverse the list again and stop at the (count/2)th node to return its value. This method requires two passes through the linked list to find the middle element.
C++ #include <iostream> using namespace std; class Node { public: int data; Node* next; Node(int x) { this->data = x; this->next = nullptr; } }; int getLength(Node* head) { int length = 0; // Count nodes in linked list while (head) { length++; head = head->next; } return length; } int getMiddle(Node* head) { // finding length of the linked list int length = getLength(head); // traverse till we reached half of length int midIndex = length / 2; while (midIndex--) { head = head->next; } return head->data; } int main() { Node* head = new Node(10); head->next = new Node(20); head->next->next = new Node(30); head->next->next->next = new Node(40); head->next->next->next->next = new Node(50); head->next->next->next->next->next = new Node(60); cout << getMiddle(head); return 0; } #include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node* next; }; int getLength(struct Node* head) { int length = 0; // find length of linked list while (head) { length++; head = head->next; } return length; } int getMiddle(struct Node* head) { // finding length of the linked list int length = getLength(head); // traverse till we reach half of the length int midIndex = length / 2; while (midIndex--) { head = head->next; } return head->data; } struct Node* createNode(int x) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = x; newNode->next = NULL; return newNode; } int main() { struct Node* head = createNode(10); head->next = createNode(20); head->next->next = createNode(30); head->next->next->next = createNode(40); head->next->next->next->next = createNode(50); head->next->next->next->next->next = createNode(60); printf("%d\n", getMiddle(head)); return 0; } class Node { int data; Node next; Node(int x) { this.data = x; this.next = null; } } class GfG { static int getLength(Node head) { int length = 0; // Count nodes in linked list while (head != null) { length++; head = head.next; } return length; } static int getMiddle(Node head) { int length = getLength(head); // traverse till we reached half of length int midIndex = length / 2; while (midIndex > 0) { head = head.next; midIndex--; } return head.data; } public static void main(String[] args) { Node head = new Node(10); head.next = new Node(20); head.next.next = new Node(30); head.next.next.next = new Node(40); head.next.next.next.next = new Node(50); head.next.next.next.next.next = new Node(60); System.out.println(getMiddle(head)); } } class Node: def __init__(self, x): self.data = x self.next = None def getLength(head): length = 0 # Count nodes in linked list while head: length += 1 head = head.next return length def getMiddle(head): length = getLength(head) # traverse till we reach half of the length midIndex = length // 2 while midIndex: head = head.next midIndex -= 1 return head.data if __name__ == "__main__": head = Node(10) head.next = Node(20) head.next.next = Node(30) head.next.next.next = Node(40) head.next.next.next.next = Node(50) head.next.next.next.next.next = Node(60) print(getMiddle(head))
using System; class Node { public int data; public Node next; public Node(int x) { this.data = x; this.next = null; } } class GfG { static int getLength(Node head) { int length = 0; // Count nodes in linked list while (head != null) { length++; head = head.next; } return length; } static int getMiddle(Node head) { int length = getLength(head); // traverse till we reach half of the length int midIndex = length / 2; while (midIndex-- > 0) { head = head.next; } return head.data; } static void Main() { Node head = new Node(10); head.next = new Node(20); head.next.next = new Node(30); head.next.next.next = new Node(40); head.next.next.next.next = new Node(50); head.next.next.next.next.next = new Node(60); Console.WriteLine(getMiddle(head)); } } class Node { constructor(x) { this.data = x; this.next = null; } } function getLength(head) { let length = 0; // Count nodes in linked list while (head) { length++; head = head.next; } return length; } function getMiddle(head) { const length = getLength(head); // traverse till we reach half of the length let midIndex = Math.floor(length / 2); while (midIndex-- > 0) { head = head.next; } return head.data; } // Driver Code const head = new Node(10); head.next = new Node(20); head.next.next = new Node(30); head.next.next.next = new Node(40); head.next.next.next.next = new Node(50); head.next.next.next.next.next = new Node(60); console.log(getMiddle(head)); [Expected Approach] Hare and Tortoise Algorithm - O(n) Time and O(1) Space
We can use the Tortoise and Hare algorithm to find the middle of the linked list.
- Initialize both slow and fast pointers at the head.
- Move slow by one step and fast by two steps each iteration.
- When fast reaches the end (or null), slow will be at the middle.
- For even nodes, slow automatically ends at the second middle.
C++ #include <iostream> using namespace std; class Node { public: int data; Node* next; Node(int x) { this->data = x; this->next = nullptr; } }; int getMiddle(Node* head) { Node* slowptr = head; Node* fastptr = head; while (fastptr != NULL && fastptr->next != NULL) { // move the fast pointer by two nodes fastptr = fastptr->next->next; // move the slow pointer by one node slowptr = slowptr->next; } return slowptr->data; } int main() { Node* head = new Node(10); head->next = new Node(20); head->next->next = new Node(30); head->next->next->next = new Node(40); head->next->next->next->next = new Node(50); head->next->next->next->next->next = new Node(60); cout << getMiddle(head) << endl; return 0; } #include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node* next; }; int getMiddle(struct Node* head) { struct Node* slowptr = head; struct Node* fastptr = head; // traverse the linked list while (fastptr != NULL && fastptr->next != NULL) { // move the fast pointer by two nodes fastptr = fastptr->next->next; // move the slow pointer by one node slowptr = slowptr->next; } return slowptr->data; } struct Node* createNode(int x) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = x; newNode->next = NULL; return newNode; } int main() { struct Node* head = createNode(10); head->next = createNode(20); head->next->next = createNode(30); head->next->next->next = createNode(40); head->next->next->next->next = createNode(50); head->next->next->next->next->next = createNode(60); printf("%d\n", getMiddle(head)); return 0; } class Node { int data; Node next; Node(int x) { this.data = x; this.next = null; } } class GfG { static int getMiddle(Node head) { Node slowptr = head; Node fastptr = head; while (fastptr != null && fastptr.next != null) { // move the fast pointer by two nodes fastptr = fastptr.next.next; // move the slow pointer by one node slowptr = slowptr.next; } return slowptr.data; } public static void main(String[] args) { Node head = new Node(10); head.next = new Node(20); head.next.next = new Node(30); head.next.next.next = new Node(40); head.next.next.next.next = new Node(50); head.next.next.next.next.next = new Node(60); System.out.println(getMiddle(head)); } } class Node: def __init__(self, x): self.data = x self.next = None def getMiddle(head): slowptr = head fastptr = head while fastptr is not None and fastptr.next is not None: # move the fast pointer by two nodes fastptr = fastptr.next.next # move the slow pointer by one node slowptr = slowptr.next return slowptr.data if __name__ == "__main__": head = Node(10) head.next = Node(20) head.next.next = Node(30) head.next.next.next = Node(40) head.next.next.next.next = Node(50) head.next.next.next.next.next = Node(60) print(getMiddle(head))
using System; class Node { public int data; public Node next; public Node(int x) { this.data = x; this.next = null; } } class GfG { static int getMiddle(Node head) { Node slowptr = head; Node fastptr = head; while (fastptr != null && fastptr.next != null) { // move the fast pointer by two nodes fastptr = fastptr.next.next; // move the slow pointer by one node slowptr = slowptr.next; } return slowptr.data; } static void Main() { Node head = new Node(10); head.next = new Node(20); head.next.next = new Node(30); head.next.next.next = new Node(40); head.next.next.next.next = new Node(50); head.next.next.next.next.next = new Node(60); Console.WriteLine(getMiddle(head)); } } class Node { constructor(new_data) { this.data = new_data; this.next = null; } } function getMiddle(head) { let slowptr = head; let fastptr = head; while (fastptr !== null && fastptr.next !== null) { // move the fast pointer by two nodes fastptr = fastptr.next.next; // Move the slow pointer by one node slowptr = slowptr.next; } return slowptr.data; } // Driver Code const head = new Node(10); head.next = new Node(20); head.next.next = new Node(30); head.next.next.next = new Node(40); head.next.next.next.next = new Node(50); head.next.next.next.next.next = new Node(60); console.log(getMiddle(head));
Explore
DSA Fundamentals
Data Structures
Algorithms
Advanced
Interview Preparation
Practice Problem
My Profile