Find Middle of the Singly Linked List in C++.

Given a singly linked list and you need to return the middle node of the list and if the list has two middle nodes then return the second middle node.

Example 1: 
Input: 1->2->3->4->5
Output: 3

Example 2:
Input: 1->0->4->7->2->3
Output: 7

This problem is very simple to solve we just need to find the length of the linked list and then divide the length by 2 to get the indexing middle node. There are multiple ways to solve the problem let's discuss them one by one.

Approach 1: Brute Force Approach.

Traverse the whole linked list to find the length of the linked list.
Calculate the position of the middle node by diving the length of the linked list by 2. (len/2)
After getting the position of the middle node traverse the linked list again using the temp pointer to find the address of the middle node.

C++ Solution Code:

/*C++ Program to find the middle element of the linked list*/
#include<bits/stdc++.h>
using namespace std;

class ListNode{
    public:
      int data;
      ListNode *next;

    //constructor
    ListNode(int data){
        this->data = data;
        this->next = NULL;
    }  
};
//creating new node
ListNode *newNode(int data){
    ListNode *temp = new ListNode(data);
    temp->next = NULL;
    return temp;
}
//Length of linked list
int getLength(ListNode *head){
    int len = 0;
    ListNode *temp = head;
    while(temp != NULL){
        temp = temp->next;
        len++;
    }
    return len;
}
//Function to get middle element
int getMiddle(ListNode* head){

    int len = getLength(head);

    ListNode *temp = head;
    int middle = len/2;

    while(middle--){
        temp = temp->next;
    }
    return temp->data;
}

int main(){
    ListNode *head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
    head->next->next->next->next = newNode(5);

    cout<<"Middle Element: "<<getMiddle(head);

    return 0;
}

Output:

Middle Element: 3

Time Complexity: O(n) + O(n/2) = O(n)
Space Complexity: O(1)

Approach 2: Two-pointer approach (Slow Fast Pointer).

The second method is known as the Tortoise and Hare method or slow and fast pointer approach. In this approach, one pointer moves faster than the other pointer, and by the time the faster pointer reaches the end of the linked list, the slower point will reach the middle of the list.

Step 1

Step 2

Step 3

Initialize two pointers, slow and fast with the head of the linked list.
Every time the slow moves one step the fast pointer move two-step at the same time.
When the fast pointer reaches the end, you need to return the value present at the slow pointer which is pointing to the middle of the list.

C++ Solution code:

/*C++ Program to find the middle element of the linked list
using slow and fast pointer approach*/
#include<bits/stdc++.h>
using namespace std;

class ListNode{
    public:
      int data;
      ListNode *next;

    //constructor
    ListNode(int data){
        this->data = data;
        this->next = NULL;
    }  
};
//creating new node
ListNode *newNode(int data){
    ListNode *temp = new ListNode(data);
    temp->next = NULL;
    return temp;
}

//Function to get middle element
int getMiddle(ListNode* head){

    ListNode *slow = head;
    ListNode *fast = head;

    while(fast && fast->next){
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow->data;
}

int main(){
    ListNode *head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
    head->next->next->next->next = newNode(5);

    cout<<"Middle Element: "<<getMiddle(head);

    return 0;
}

Output:

Middle Element: 3

Time Complexity: O(n/2) = O(n)
Space Complexity: O(1)

Related Articles:

Convert Binary Linked List to Integer.

Reverse a Singly Linked List in C++.

Merge Two Sorted Linked List in C++.

Intersection Point of Two Linked Lists in C++.

Detect Cycle in a Linked List in C++.

Find Middle of the Singly Linked List in C++.

No comments:

Post a Comment