GO Classes DPP | GATE CS | Data Structures | Find Middle Node

Answer 1

We'll be using the using the optimal Two-Pointer (Tortoise and Hare Algorithm)

 

Let's define an "access" as a pointer moving to or landing on a node.

1. Initialization: Both the $\texttt{slow}$ and $\texttt{fast}$ pointers start at the head of the list $($Node $1)$.

   • Accesses $= 2$

2. The Loop: In each step of the traversal:

   • The $\texttt{fast}$ pointer moves forward $2$ nodes (e.g., from Node $1 \rightarrow$ Node $2 \rightarrow$ Node $3)$. This requires reading the links sequentially. $(2$ accesses$)$

   • The $\texttt{slow}$ pointer moves forward $1$ node $($e.g., from Node $1 \rightarrow$ Node $2)$. $(1$ access$)$

   • Total accesses per iteration $=3$

3. Number of Iterations: To reach the end of an $n$-length list, the fast pointer takes $n−1$ steps. Since it takes $2$ steps per iteration, there are exactly $\dfrac{n−1​}{2}$​ iterations.

 

Now, 

Total Accesses $= ($Initial accesses$) + ($Iterations $\times$ Accesses per iteration$)$

Total Accesses$=2+\dfrac{(n−1​)}{2}\times3$

Total Accesses$=\dfrac{4+3n−3​}{2}=\dfrac{3n+1​}{2}$

Now, because the problem specifies integer division, for any odd $n$, 

the expression $\dfrac{3n+1​}{2}$​ yields the exact same integer result as $\dfrac{3n+2}{2}$​.

 

Answer : D

Answer 2

Code for Slow Pointer / Fast Pointer approach for optimal position accesses.

 

MiddleNode(head):
    slow = head
    fast = head

    while true:
        A = fast.next
        if A == NULL:
            return slow

        B = A.next
        if B == NULL:
            return slow

        fast = B
        slow = slow.next

 

Answer: D