{"post":"

Find the Middle value of a Linked List

THEORY:

Calculating the middle value of linked list gives us a single value only when there are odd number of elements in the list.

If there are even number of nodes, then there would be two middle nodes, and we print the second middle element.

For example, if the given linked list is 1->2->3->4->5->6 then output should be 4.

GIVEN PROBLEM: Find the middle element of a Linked List

# Algorithm

We intend to do as follows:

Create a linked list
Create some nodes of this list.
Iterate with two indices:\n
1. One iterates by two steps i.e. over two nodes
2. One iterates over one node
\n
When the index iterating two steps reaches the end, we will be at our middle element.

Code

#include <iostream>\nusing namespace std;\n\nstruct Node\n{\n    int data;\n    Node * next;\n\n};\n\nvoid printMiddle(struct Node *head)\n{\n    int count = 0;\n    struct Node *mid = head;\n    while (head != NULL)\n    {\n        if (count & 1)\n            mid = mid->next;\n        ++count;\n        head = head->next;\n    }\n    if (mid != NULL)\n        cout << \"The middle element is \" << mid->data;\n}\n\nint main()\n{\n    Node *head = NULL;\n    Node *second = NULL;\n    Node *third = NULL;\n    Node *fourth = NULL;\n    Node *fifth = NULL;\n    head = new Node();\n    second = new Node();\n    third = new Node();\n    fourth = new Node();\n    fifth = new Node();\n    head->data = 2;\n    second->data = 16;\n    third->data = 13;\n    fourth->data = 1;\n    fifth->data = 34;\n    head->next = second;\n    second->next = third;\n    third->next = fourth;\n    fourth->next = fifth;\n    fifth->next = NULL;\n    printMiddle(head);\n    return 0;\n}\n\n

OUTPUT:

The middle element is 13\n\n

For even number of elements, we increase the number of nodes and insert another 5 in the linked list. Then the program’s output will be (after adding changes to linked list – no changes to function):

\n","title":"Find the Middle value of a Linked List","authorDetails":{"name":"Anshuman Raina","slug":"anshuman-raina"},"description":"Learn how to find the middle element of a linked list in C++. The printMiddle function iterates through the list and keeps track of the number of elements visited, updating the middle element whenever the number of elements is odd. ","slug":"find-the-middle-value-of-a-linked-list/","articleId":"636a83417bb1ce5072622b53","bookmarkStatus":{"isBookmarked":false,"bookmarkId":null}}