# Find the middle element of the linked list in single pass – O(n) complexity

Create a Node – A node consists of data of that node and some information about the next linked node

```function Node(data, nextNode){
this.data = data;
this.nextNode = nextNode;
}```

Create all nodes

Note: First Node from right. This would be our last node in sequence. The reference to next node would be null since this is our last node.

```var n5 = new Node("5", null);
var n4 = new Node("4", n5);
var n3 = new Node("3", n4);
var n2 = new Node("2", n3);
var n1 = new Node("1", n2);
```

// So here is the representation of the linked list nodes, that we just created.
// n1 (1, n2) –> n2 (2, n3) –> n3 (3, n4) –> n4 (4, n5) –> n5 (5, null)

Here is how the linked list looks

The Naive Solution to this problem would be in 2 passes (2 for loops), which takes O(n^2) worst case complexity

1st pass is to loop thru to get the count of nodes in linked list and
2nd pass is to loop thru find the middle element by dividing the Count of Nodes by 2

So, for example if there are 5 Nodes.

1st pass is to count the number of nodes = 5
2nd pass is to loop thru to get the middle element by dividing 5/2 = 2.5 (so in the middle element to be 3)

There is a better and a faster way to get this in 1 Pass (1 for/while loop), with O(n) complexity

Assign 2 pointers while looping.
1st pointer moves 1 element at a time.
2nd pointer moves 2 elements at a time (twice as faster as the 1st pointer)

Some theory/story:

Assume that Person A and Person B would like to reach a destination X from same starting point.

Assume that it would actually take 10 mins to reach destination X.

Assume that Person B walks 2 times faster than Person A, then by the time Person B reaches destination X, Person A is exactly half way thru.

So, lets give a starting point to our node n1.

```var slowNode = n1;
var fastNode = n1;

// Check if nextNode is not null and nextNode of the nextNode
// (2 Nodes from the current Node) is also not null
while(fastNode.nextNode != null && fastNode.nextNode.nextNode != null) {
// slowNode should be moving to the next element of the linked list sequentially
slowNode = slowNode.nextNode;
// Now the fastNode should be twice as faster as the slowNode
fastNode = fastNode.nextNode.nextNode;
}

console.log(slowNode.data);
```

Relevant Code using Java

```public class MiddleElementLinkedList {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

// Set the starting point

while(fastNode.getNextNode() != null && fastNode.getNextNode().getNextNode() != null){
slowNode = slowNode.getNextNode();
fastNode = fastNode.getNextNode().getNextNode();
}

System.out.println("Middle Element: " + slowNode.getData());

}

private String data;
/**
* @return the data
*/
public String getData() {
return data;
}

/**
* @param data the data to set
*/
public void setData(String data) {
this.data = data;
}

/**
* @return the nextNode
*/
return nextNode;
}

/**
* @param nextNode the nextNode to set
*/
if(nextNode == null)
this.nextNode = null;
this.nextNode = nextNode;
}