C++ Linked List Exercises: Find middle element in a single linked list
6. Find the Middle Element of a Linked List
Write a C++ program to find the middle element of a given Linked List.
Test Data:
Original list:
9 7 5 3 1
Middle element of the said list:
5
Original list:
7 5 3 1
Middle element of the said list:
3
Explanation: The second node of the list is returned since it has the values 5 and 3.
Sample Solution:
C++ Code:
#include <iostream> // Including input-output stream header file
using namespace std; // Using standard namespace
// Structure for defining a Node
struct Node {
int num; // Data field to store a number
Node *next; // Pointer to the next node
}; // Node constructed
int sz = 0; // Initializing variable to keep track of the size of the linked list
// Function to insert a node at the beginning of the linked list
void insert(Node** head, int num) {
Node* new_Node = new Node(); // Creating a new node
new_Node->num = num; // Assigning data to the new node
new_Node->next = *head; // Pointing the new node to the current head
*head = new_Node; // Making the new node as the head
sz++; // Increasing the size of the linked list
}
// Function to find the middle element of a linked list
int get_Middle(Node *head) {
if (!head) return -1; // If the list is empty, return -1 (no middle element)
int c = 0; // Counter variable to keep track of the position in the list
Node *middle = head; // Pointer for the middle element initially set to head
while (head) {
if (c % 2 != 0) middle = middle->next; // Update the middle pointer for odd positions
c++; // Incrementing the counter
head = head->next; // Move to the next node
}
return middle->num; // Return the value of the middle element
}
// Display all nodes in the linked list
void display_all_nodes(Node* node) {
while (node != NULL) {
cout << node->num << " "; // Displaying the data in the current node
node = node->next; // Move to the next node
}
}
int main() {
Node* head = NULL; // Initializing the head of the linked list as NULL
insert(&head, 1); // Inserting a node with value 1
insert(&head, 3); // Inserting a node with value 3
insert(&head, 5); // Inserting a node with value 5
insert(&head, 7); // Inserting a node with value 7
cout << "Original list:\n"; // Displaying message for the original list
display_all_nodes(head); // Displaying all nodes in the original list
cout << "\nMiddle element of the said list:"; // Displaying message for the middle element
cout << "\n" << get_Middle(head) << "\n"; // Finding and displaying the middle element
cout << "\nOriginal list:\n"; // Displaying message for the updated list after insertion
insert(&head, 9); // Inserting a node with value 9
display_all_nodes(head); // Displaying all nodes in the updated list
cout << "\nMiddle element of the said list:"; // Displaying message for the middle element
cout << "\n" << get_Middle(head); // Finding and displaying the middle element in the updated list
cout << endl; // Displaying newline
return 0; // Returning from the main function
}
Sample Output:
Original list: 7 5 3 1 Middle element of the said list: 3 Original list: 9 7 5 3 1 Middle element of the said list: 5
Flowchart:
For more Practice: Solve these Related Problems:
- Write a C++ program to determine the middle element of a singly linked list by using two-pointer technique.
- Develop a C++ program that finds and displays the middle element of a linked list even when the list has an even number of nodes.
- Design a C++ program to compute the middle element of a linked list and display both the value and its node position.
- Implement a C++ program to identify the middle element of a linked list using a recursive approach and then print the result.
CPP Code Editor:
Contribute your code and comments through Disqus.
Previous C++ Exercise: Insert a new node at the end of a Linked List.
Next C++ Exercise: Insert new node at the middle of a Singly Linked List.
What is the difficulty level of this exercise?