Find the Middle value of a Linked List

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:

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

Code

#include <iostream>
using namespace std;

struct Node
{
    int data;
    Node * next;

};

void printMiddle(struct Node *head)
{
    int count = 0;
    struct Node *mid = head;
    while (head != NULL)
    {
        if (count & 1)
            mid = mid->next;
        ++count;
        head = head->next;
    }
    if (mid != NULL)
        cout << "The middle element is " << mid->data;
}

int main()
{
    Node *head = NULL;
    Node *second = NULL;
    Node *third = NULL;
    Node *fourth = NULL;
    Node *fifth = NULL;
    head = new Node();
    second = new Node();
    third = new Node();
    fourth = new Node();
    fifth = new Node();
    head->data = 2;
    second->data = 16;
    third->data = 13;
    fourth->data = 1;
    fifth->data = 34;
    head->next = second;
    second->next = third;
    third->next = fourth;
    fourth->next = fifth;
    fifth->next = NULL;
    printMiddle(head);
    return 0;
}

OUTPUT:

The middle element is 13

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):