# Find the middle of a given linked list data structure

### Question: In given a Linked List,  find the middle of the list and print the number.

Input : -> 4-> 2-> 7-> 9-> 1

Output : 7

Before starting you have to must know about Linked list and how to create it and Inserting node (data) in LinkedList.

There is many approach to find middle number in LinkedList.

### 1.  Single pointer approach

In this approach, we will scan the entire list and count the number of nodes. We divide the number by 2 and then again traverse the list up to that node.

```package in.eyehunt.data.struc;
class Node {
int data;
Node next;
// Parameterized constructor
Node(int d) {
data = d;
next = null;
}
}
void push(int n) {
//create new node
Node newNode = new Node(n);
// move had point to new node
}
void findMiddleNode() {
} else {
int middleNode = (count() % 2 == 0) ? (count() / 2) : ((count() + 1) / 2);

int countNodes = 0;
while (countNodes != middleNode -1) {
pointerNode = pointerNode.next;
countNodes ++;
}
System.out.println("\nMiddle node of linked List is " + middleNode);
System.out.println("Middle node data is " + pointerNode.data);
}
}
//Returns count of nodes in linked list (iteration)
public int count() {
int a = 0;
while (n != null) {
n = n.next;
a++;
}
return a;
}
void printAllNodes() {
while (node != null) {
System.out.print("-> " + node.data);
node = node.next;
}
}
public static void main(String a[]) {
//create a simple linked list with 4 nodes
}
}```

Output : -> 4-> 2-> 7-> 9-> 1
Middle node of linked List is 3
Middle node data is 7

`Time Complexity: Time for finding the length of list + Time for locating middle node = O(n) + O(n) ≈ O(n)`
`Space Complexity: O(1)`

### 2. Using 2 pointers

With 2 pointers to traverse the list ,we can find the middle of list with only one scan on the Linked List.

• pointer1 travels one node at a time
• pointe2 travels two nodes a time.

Thus, when pointe2 reaches the end of the Linked List, pointer1 will point at the middle of the Linked List.

```package in.eyehunt.data.struc;
class Node {
int data;
Node next;
// Parameterized constructor
Node(int d) {
data = d;
next = null;
}
}
void push(int n) {
//create new node
Node newNode = new Node(n);
// move had point to new node
}
void findMiddleNode() {
} else {

while (pointer2 != null && pointer2.next != null) {
pointer1 = pointer1.next;
pointer2 = pointer2.next.next;
}
System.out.println("\nMiddle node data is " + pointer1.data);
}
}
void printAllNodes() {
while (node != null) {
System.out.print("-> " + node.data);
node = node.next;
}
}
public static void main(String a[]) {
//create a simple linked list with 4 nodes
}
}```

Output: -> 4-> 2-> 7-> 9-> 1
Middle node data is 7

`Time Complexity: O(n)`
`Space Complexity: O(1)`

here is more LinkedList interview questions :