🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.
▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube
▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube
1. Introduction
In computer science, a linked list is a sequence of data structures, which are connected together via links. Linked lists are among the simplest and most common data structures. One common problem is to find the middle element of a linked list.
In this blog post, we will learn how to write a C++ program to find the middle of the Linked List.
2. Program Overview
To find the middle of a linked list, we can use two pointers: one moving one step at a time and the other moving two steps. When the faster pointer reaches the end of the list, the slower pointer will be in the middle.
3. Code Program
#include<iostream>
using namespace std;
// Define a Node for the linked list
class Node {
public:
int data; // Data contained in the node
Node* next; // Pointer to the next node in the list
// Constructor to initialize node data and set next pointer to nullptr
Node(int val): data(val), next(nullptr) {}
};
// Define a Singly Linked List
class LinkedList {
private:
Node* head; // Pointer to the start (head) of the list
public:
// Constructor to initialize an empty list with head as nullptr
LinkedList(): head(nullptr) {}
void push(int new_data); // Add a node to the beginning of the list
void printMiddle(); // Print the middle element of the list
};
// Function to add a new node at the beginning of the list
void LinkedList::push(int new_data) {
Node* new_node = new Node(new_data); // Create a new node with given data
new_node->next = head; // Make the new node point to the current head
head = new_node; // Update the head to point to the new node
}
// Function to print the middle element of the linked list
void LinkedList::printMiddle() {
Node* slow_ptr = head; // Slow pointer: Moves one step at a time
Node* fast_ptr = head; // Fast pointer: Moves two steps at a time
if (head != nullptr) {
// Traverse the list. By the end, the slow pointer will be at the middle
while (fast_ptr != nullptr && fast_ptr->next != nullptr) {
fast_ptr = fast_ptr->next->next; // Move by two nodes
slow_ptr = slow_ptr->next; // Move by one node
}
cout << "The middle element is [" << slow_ptr->data << "]" << endl;
}
}
int main() {
LinkedList ll; // Create an empty linked list
// Push elements into the linked list and print the middle after each insertion
for (int i = 5; i > 0; i--) {
ll.push(i);
ll.printMiddle();
}
return 0;
}
Output:
The middle element is [5] The middle element is [4] The middle element is [4] The middle element is [3] The middle element is [3]
4. Code Explanation
The LinkedList class consists of two methods:
1. push, which inserts a new element at the beginning.
2. printMiddle, which prints the middle of the linked list.
The printMiddle method uses the slow_ptr and fast_ptr technique. As the fast_ptr traverses the list two steps at a time and the slow_ptr one step at a time, by the time fast_ptr reaches the end of the list, slow_ptr will be pointing to the middle of the linked list.
My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:
Build REST APIs with Spring Boot 4, Spring Security 7, and JWT
![[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25](https://img-c.udemycdn.com/course/750x422/6852721_b512_2.jpg "[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25")
[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25
ChatGPT + Generative AI + Prompt Engineering for Beginners
Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)
Available in Udemy for Business
Building Real-Time REST APIs with Spring Boot - Blog App
Available in Udemy for Business
Building Microservices with Spring Boot and Spring Cloud
Available in Udemy for Business
Java Full-Stack Developer Course with Spring Boot and React JS
Available in Udemy for Business
Build 5 Spring Boot Projects with Java: Line-by-Line Coding
Testing Spring Boot Application with JUnit and Mockito
Available in Udemy for Business
Spring Boot Thymeleaf Real-Time Web Application - Blog App
Available in Udemy for Business
Master Spring Data JPA with Hibernate
Available in Udemy for Business
Spring Boot + Apache Kafka Course - The Practical Guide
Available in Udemy for Business
Comments
Post a Comment
Leave Comment