---
###### tags: `Leetcode`
---
# Leetcode 876. Middle of the Linked List

[link](https://leetcode.com/problems/middle-of-the-linked-list/)

---

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.

#### 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 <= Node.val <= 100

---

We initialize an empty dictionary called d and a counter variable n to 0.

Then it enters a loop that iterates through each node in the linked list. For each node, it adds the node to the dictionary with its corresponding index (starting at 0) as the key. It then increments n.

If the current node is the last node in the linked list, the method has reached the end of the linked list and it returns the middle node by retrieving it from the dictionary using the expression d[n//2].

If the current node is not the last node, the loop continues to the next node by updating head to head.next.

If the input linked list is empty (head is None), the method will return None.

#### Solution 1

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        d = {}
        n = 0
        
        while head:
            d[n] = head
            n += 1
            if head.next is None:
                return d[n//2]

            head = head.next

O(T): O(n)
O(S): O(n)

---

The method uses two pointers, slow and fast, to traverse the linked list. Both pointers are initially set to the head of the linked list.

The method then enters a while loop with two conditions: fast and fast.next should not be None (i.e., there are at least two nodes remaining in the linked list). The fast pointer moves two steps ahead, while the slow pointer moves one step ahead in each iteration.

Inside the loop, the method checks if the fast pointer is equal to the slow pointer. If they are equal, it means the linked list has a cycle, and the loop is broken. This is done to avoid an infinite loop in case of a cyclic linked list.

After breaking the loop, the method returns the slow pointer, which points to the middle node of the linked list.

#### Solution 2: Two pointers

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow, fast = head, head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                break

        return slow

O(T): O(n)
O(S): O(1)