Middle of Linked List

# Middle of Linked List ## Difficulty Easy ## Tags `linked list`, `two pointers` ## Problem Statement Given the head of a singly linked list, return the middle node. If there are two middle nodes, return the **second middle** node. ## Constraints - The number of nodes in the list is in the range [1, 100]. - 1 ≤ Node.val ≤ 100 ## Signatures ### Python ```python def middle_node(head: ListNode) -> ListNode: pass ``` ### Java ```java public class Solution { public ListNode middle_node(ListNode head) { return null; } } ``` ### Csharp ```csharp public class Solution { public ListNode middle_node(ListNode head) { throw new NotImplementedException(); } } ``` ### Cpp ```cpp class Solution { public: ListNode* middle_node(ListNode* head) { } }; ``` ### C ```c ListNode* middle_node(ListNode* head) { } ``` ### Ruby ```ruby def middle_node(head) end ``` ### Perl ```perl sub middle_node { my ($self, @args) = @_; } ``` ### Scala ```scala object Solution { def middle_node(head: ListNode): ListNode = { } } ``` ### Haskell ```haskell middle_node :: ... -> ... middle_node args = undefined ``` ### Clojure ```clojure (defn middle_node [head] ) ``` ### Scheme ```scheme (define (middle_node head) ) ``` ## Examples ### Example 1 **Input:** ``` head = [1, 2, 3, 4, 5] ``` **Output:** ``` [3, 4, 5] ``` **Explanation:** The middle node is 3. Return node with value 3. ### Example 2 **Input:** ``` head = [1, 2, 3, 4, 5, 6] ``` **Output:** ``` [4, 5, 6] ``` **Explanation:** There are two middle nodes (3 and 4). Return the second one (4). ### Example 3 **Input:** ``` head = [1] ``` **Output:** ``` [1] ``` ## Hints 1. Use the "slow and fast pointer" (tortoise and hare) technique. 2. Initialize both pointers to head. 3. Move slow one step, fast two steps. 4. When fast reaches the end (null or last node), slow is at the middle.