Question:

How to find the middle item in a linked list?

Summary:

This C++ code defines a solution to find the middle element of a linked list. It utilizes the "two-pointer" technique, where two pointers traverse the linked list at different speeds.

Solution:

/* Link list Node

struct Node {

int data;

Node* next;

Node(int x){

data = x;

next = NULL;

}

}; */

class Solution{

public:

/* Should return data of middle node. If linked list is empty, then -1*/

int getMiddle(Node *head)

{

// Your code here

if(head == NULL)

return -1;

if(head ->next == NULL)

return head ->data;

Node* faster=head;

Node* slower = head;

int lenght = 0;

while(faster ->next != NULL)

{

lenght++;

if(faster->next->next != NULL)

faster = faster->next->next;

else

faster = faster->next;

slower = slower->next;

}

return slower ->data;

}

};

Explanation:

The function first checks if the linked list is empty (head == NULL). If so, it returns -1, indicating an empty list.
If there's only one node in the linked list (head->next == NULL), the data of that single node is returned.
Two pointers, faster and slower, are initialized to the head of the linked list. The length variable is used to keep track of the number of nodes visited.
The while loop continues until the faster pointer reaches the end of the linked list. In each iteration, the slower pointer moves one step, and the faster pointer moves either two steps (if faster->next->next != NULL) or one step.
The slower pointer ends up pointing to the middle node of the linked list when the loop terminates.
The data of the middle node (slower->data) is then returned.