Middle Element of A Singly Linked List

Before Moving To Solution , I would suggest you to first try this question through below link.

Problem Link

Statement :

You are given a linked list you have to output the middle element of the linked list.

Example 1:

Input:

head = [1,2,3,4,5]

Output:

3

Explanation:

The middle node of the list is node 3.

Example 2:

Input:

head = [1,2,3,4,5,6]

Output:

4 or 3

Explanation:

Since the list has two middle nodes with values 3 and 4, we can return anyone of them.

Constraints:

• The number of nodes in the list is in the range [1, 100].
• 1 <= Node.val <= 100

Solution

Method : 1(Brute Force Solution)

• Make a curr pointer and iterate through list and calculate Length of linked list
• make a variable and iterate through linked list again and terminate the loop when variable becomes equal to length/2.
• return the current node data

Implementation

#include <bits/stdc++.h>
using namespace std;
struct Node
{
    int data;
    Node *next;
    Node(int x)
    {
        data = x;
        next = NULL;
    }
};

Node *insert(Node *ptr, int v)
{
    Node *temp = new Node(v);
    if (ptr == NULL)
    {
        return temp;
    }
    Node *head = ptr;
    while (head->next != NULL)
    {
        head = head->next;
    }
    head->next = temp;
    return ptr;
}
int Middle(Node *head)
{
    if (head == NULL)
    {
        return -1;
    }
    int count = 0;
    Node *curr = head;
    while (curr != NULL)
    {
        count++;
        curr = curr->next;
    }
    curr = head;
    int i = 1;
    while (i <= count / 2)
    {
        curr = curr->next;
        i++;
    }
    return curr->data;
}

void print(Node *m)
{
    while (m != NULL)
    {
        cout << m->data << " -> ";
        m = m->next;
    }
    cout << endl;
}
int main()
{
    Node *head = NULL;
    int n;
    cout << "Enter the size of the linked list : ";
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int c;
        cin >> c;
        head = insert(head, c);
    }
    print(head);

    if (Middle(head) == -1)
    {
        cout << "linked list is empty." << endl;
    }
    else
    {
        cout << "Middle element of given linked list is : " << Middle(head) << endl;
    }
    return 0;
}

• Time Complexity : O(N)
• N : number of nodes in linked list
• Space Complexity : O(1)

Method : 2 (Two Pointer Approach )

• Use two pointer ptr1 and ptr2.
• ptr2 jump two nodes at a time and ptr1 jump one node at a time.
• iterate untill ptr2==NULL or pt2->next == NULL
• return ptr1->data

Implementation

#include <bits/stdc++.h>
using namespace std;
struct Node
{
    int data;
    Node *next;
    Node(int x)
    {
        data = x;
        next = NULL;
    }
};

Node *insert(Node *ptr, int v)
{
    Node *temp = new Node(v);
    if (ptr == NULL)
    {
        return temp;
    }
    Node *head = ptr;
    while (head->next != NULL)
    {
        head = head->next;
    }
    head->next = temp;
    return ptr;
}
int Middle(Node *head)
{
    if (head == NULL)
    {
        return -1;
    }
    Node *ptr1 = head;
    Node *ptr2 = head;
    while (ptr2 != NULL and ptr2->next != NULL)
    {
        ptr1 = ptr1->next;
        ptr2 = ptr2->next->next;
    }
    return ptr1->data;
}

void print(Node *m)
{
    while (m != NULL)
    {
        cout << m->data << " -> ";
        m = m->next;
    }
    cout << endl;
}
int main()
{
    Node *head = NULL;
    int n;
    cout << "Enter the size of the linked list : ";
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int c;
        cin >> c;
        head = insert(head, c);
    }
    print(head);

    if (Middle(head) == -1)
    {
        cout << "linked list is empty." << endl;
    }
    else
    {
        cout << "Middle element of given linked list is : " << Middle(head) << endl;
    }
    return 0;
}

• Time Complexity : O(N/2)
• N : number of nodes in linked list
• Space Complexity : O(1)