# Find the middle of a Linked List

## Problem:

Given a singly linked list of N nodes. The task is to find the middle of the linked list. For example, if given linked list is 1->2->3->4->5 then the output should be 3.

If there are even nodes, then there would be two middle nodes, we need to print the second middle element. For example, if given linked list is 1->2->3->4->5->6 then the output should be 4.

### Example 1:

Input:

Output:

Explanation:

Middle of linked list is 3.

### Example 2:

Input:

Output:

Explanation:

Middle of linked list is 7.

The task is to complete the function getMiddle() which takes a head reference as the only argument and should return the data at the middle node of the linked list.

Expected Time Complexity: O(N).

Expected Auxiliary Space: O(1).

## Solutions

### Java Code

```import java.util.*;
import java.io.*;

class Node{
int data;
Node next;

Node(int x){
data = x;
next = null;
}

}
class CB{
static void printList(Node node)
{
while (node != null)
{
System.out.print(node.data + " ");
node = node.next;
}
System.out.println();
}
public static void main(String args[]) throws IOException {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t > 0){
int n = sc.nextInt();
for(int i=0; i<n-1; i++)
{
tail.next = new Node(sc.nextInt());
tail = tail.next;
}
Solution g = new Solution();
System.out.println(ans);
t--;
}
}
}
// } Driver Code Ends

/* Node of a linked list
class Node {
int data;
Node next;
Node(int d)  { data = d;  next = null; }
}
*/

class Solution
{
{
while(fast!=null && fast.next!=null)
{
fast=fast.next.next;
slow = slow.next;
}
return slow.data;
}
}
```

### C++ Code:

```#include <bits/stdc++.h>
using namespace std;

struct Node
{
int data;
struct Node* next;

Node(int x){
data = x;
next = NULL;
}
};
void printList(Node* node)
{
while (node != NULL) {
cout << node->data <<" ";
node = node->next;
}
cout<<"\n";
}
/* Function to get the middle of the linked list*/
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;

int data;
cin>>data;
struct Node *head = new Node(data);
for (int i = 0; i < n-1; ++i)
{
cin>>data;
tail->next = new Node(data);
tail = tail->next;
}
}
return 0;
}

// } Driver Code Ends

struct Node {
int data;
Node* next;

Node(int x){
data = x;
next = NULL;
}

}; */

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