# leetcode 876, middle node of linked list (fast and slow pointer method)

Given a non empty single linked list with head node, the middle node of the linked list is returned.

If there are two intermediate nodes, the second intermediate node is returned.

Example 1:

Input: [1,2,3,4,5]
Output: node 3 in this list (serialization form: [3,4,5])
The returned node value is 3. (the serialization expression of the evaluation system for this node is [3,4,5]).
Note that we return an object ans of type ListNode, as follows:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL

Example 2:

Input: [1,2,3,4,5,6]
Output: node 4 in this list (serialization form: [4,5,6])
Since the list has two intermediate nodes with values of 3 and 4, we return the second node.

Tips:

The number of nodes in a given list is between 1 and 100.

My simple idea: traverse twice

```/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
int total = 0;
while (cur != null) {
total++;
cur = cur.next;
}
for(int i = 0; i < total / 2; i++) {
cur = cur.next;
}
return cur;
}
}
```

Other ideas:

I. output to array and solve the problem with index

```/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
ListNode[] cur = new ListNode;
int total = 0;
}
return cur[total / 2];
}
}
```

II. Fast and slow pointer method

When traversing a list with a slow pointer, it's twice as fast to let the other pointer fast. When fast reaches the end of the list, slow must be in the middle.

```/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {