###### tags: `leetcode` `easy` `Linked List` `Two Pointers`
# [876. Middle of the Linked List](https://leetcode.com/problems/middle-of-the-linked-list/)

## Description

Given the **head** of a singly linked list, return *the middle node of the linked list*.

If there are two middle nodes, return **the second middle node**.

## Examples
### Example 1:

**Input**: head = [1,2,3,4,5]
**Output**: [3,4,5]
**Explanation**: The middle node of the list is node 3.

### Example 2:

**Input**: head = [1,2,3,4,5,6]
**Output**: [4,5,6]
**Explanation**: Since the list has two middle nodes with values 3 and 4, we return the second one.

## Constraints:

- The number of nodes in the list is in the range `[1, 100]`.
- $1 \leq Node.val \leq 100$ .

## Code

- Way 1 :

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* middleNode(struct ListNode* head){
    struct ListNode *fast, *slow;
    for(fast = head, slow = head;;){
        // Wether we can jump to the next node
        if(fast->next != NULL){
            // Whether we can jump two nodes?If we can, jump and set slow pointer
            if((fast->next)->next != NULL){
                fast = (fast->next)->next;
                slow = slow->next;
            }
            // If we can only jump ome node, it means the link-list has even nodes and slow is the first middle
            else
                return slow->next;
        }
        // If we can not jump to the next node, it means we have odd nodes and slow is the middle
        else
            return slow;
    }
}

- Way 2 :

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* middleNode(struct ListNode* head){
    int count;
    struct ListNode *tmp;
    for(count = 0, tmp = head ; tmp ; count++)
        tmp = tmp->next;
    count /= 2;
    for(int i = 0 ; i < count ; i++)
        head = head->next;
    return head;
}

## Complexity

- Way 1 & 2:

|Space |Time |
|- |- |
|$O(1)$|$O(N)$|

## Result

- Way 1 :
- Runtime: 4 ms, faster than 32.41%
- Memory Usage: 6 MB, less than 7.74%
- Way 2 :
- Runtime: 0 ms, faster than 100.00%
- Memory Usage: 5.9 MB, less than 52.55%