Find the Middle of a List in a Single Pass

Given a Singly-Linked List, write a method - findMiddleNode that finds and returns the middle node of the list in a single pass.

Examples:
1 ==> 1
1->2 ==> 1
1->2->3->4 ==> 2
1->2->3->4->5 ==> 3

Need a hand? Try out these hints, one at a time.

Quick hint to get things rolling

The slow-fast pointer approach is very useful for finding the middle nodes of Linked Lists in a single pass.

Final hint! You should be able to code the problem on viewing this.

1. Traverse the list by moving over one reference with twice the speed as that of the of the other reference :
slow = slow.next
fast = (fast.next).next

2. Stop the traversal when the faster ListNode reference reaches the end of the linked list.

3. The slower node will invariably be pointing to the middle ListNode. Return slow

public ListNode findMiddleNode(ListNode head) {


}

This Coding Interview Question is available with an answer in the following programming languages :

Java

Python

Find the Middle of a List in a Single Pass

Quick hint to get things rolling

Final hint! You should be able to code the problem on viewing this.

The interview prep tool you'll fall in love with!

This Coding Interview Question is available with an answer in the following programming languages :