Slow and Fast Pointers LinkedList Solution (with step by step explanation)
Intuition\nWe will use slow and fast pointers to find middle node.\n# Approach\nwe create slow and fast pointer at start and point them to head, after that we s
# Intuition\nWe will use slow and fast pointers to find middle node.\n# Approach\nwe create slow and fast pointer at start and point them to head, after that we start iterating until fast pointer next will point at null. On each iteration we move slow pointer by one node and fast node by twice as much, so when fast pointer will reach end of LinkedList, slow pointer will be pointing right at middle node in LinkedList\n# Complexity\n- Time complexity:\nO(logn) -> we iterate n / 2 because we move fast pointer at x2 per node\n- Space complexity:\nO(1) -> we use two variables to store pointers to fast and slow nodes\n# Code\n```\n/**\n * Definition for singly-linked list.\n * class ListNode {\n *     val: number\n *     next: ListNode | null\n *     constructor(val?: number, next?: ListNode | null) {\n *         this.val = (val===undefined ? 0 : val)\n *         this.next = (next===undefined ? null : next)\n *     }\n * }\n */\n\nfunction middleNode(head: ListNode | null): ListNode | null {\n    // declare slow pointer and point to head\n    let slow = head\n    // declare fast pointer and point to head\n    let fast = head\n    // iterate until fast node next pointer will point to null:\n    while(fast && fast.next) {\n        // move slow pointer to next node\n        slow = slow.next;\n        // move fast pointer at x2 speed from slow pointer\n        fast = fast.next.next;\n    }\n    // return slow pointer which will point to middle of LinkedList\n    return slow\n};\n```
['Linked List', 'TypeScript']