Problem Statement:
You are given an single LL.
You need to fing the middle element.
Example
Input : 1->2->3->4->5->6 Output : 4
Solution
The solution is very simple.
We take 2 pointers, Fast and Slow.
Fast will move 2 places at a time.
Slow will move 1 place at a time.
When fast pointer reaches to end of the LL, slow pointer will be pointing to the middle element.
Solution in C++
#include <vector> #include <algorithm> //visit www.ProDeveloperTutorial.com for 450+ solved questions #include <iostream> #include <string> #include <unordered_map> #include <vector> #include <sstream> using namespace std; #include<iostream> #include<vector> using namespace std; struct Node { int data; struct Node* next; }; void insert_at_begenning ( struct Node **head_pointer, int data) { // allocate memory for new node struct Node *temp_node = (struct Node*) malloc(sizeof(struct Node)); // assign the data to new node temp_node->data = data; // initialize the new node to point to NULL temp_node->next = NULL; // if this is the first pointer, then this is the head pointer if (*head_pointer == NULL) { *head_pointer = temp_node; } else { // point the next of the present pointer to the head pointer temp_node->next = *head_pointer; //then move the reference of head pointer to the current pointer *head_pointer = temp_node; } } void display_list(struct Node **head_pointer) { // take a reference to head pointer for navigation struct Node *temp = *head_pointer; while(temp != NULL) { if(temp->next != NULL) printf("%d -> ", temp->data); else printf("%d", temp->data); //navigate to next pointer temp = temp->next; } printf("\n"); } void middleNode(Node* head) { Node* slow=head; Node* fast =head; while(fast!=NULL&& fast->next!=NULL) { fast = fast->next->next; slow = slow->next; } cout<<"The middle node is\n"<<slow->data<<endl;; } int main() { struct Node *list_1 = NULL; Node *result = NULL; insert_at_begenning(&list_1,1); insert_at_begenning(&list_1,3); insert_at_begenning(&list_1,2); insert_at_begenning(&list_1,1); printf("Original List\n"); display_list(&list_1); middleNode(list_1); return 0; }
Output:
Original List 1 -> 2 -> 3 -> 1 The middle node is 3