Middle of Linked List | Dataford Interview Questions

A Cloudera data-processing component stores an ordered stream as a singly linked list. Given the list head, return the value of its middle node using a single traversal.

If the list contains an even number of nodes, return the second of the two middle nodes. The list is represented using nested dictionaries: each node has an integer value and a next field containing another node or None.

Formal Specification

Implement find_middle(head), where head is either None or a node represented as {"value": integer, "next": node_or_none}. Return the integer value stored in the middle node. You may use only constant auxiliary space, excluding the input list.

Constraints

0 <= n <= 10^5
-10^9 <= node.value <= 10^9
The list contains no cycles
Return the second middle node when n is even

Function Signature

def find_middle(head):

Your question is Middle of Linked List. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem